/**************************************************************************\
|
|    Copyright (C) 2009 Marc Stevens
|
|    This program is free software: you can redistribute it and/or modify
|    it under the terms of the GNU General Public License as published by
|    the Free Software Foundation, either version 3 of the License, or
|    (at your option) any later version.
|
|    This program is distributed in the hope that it will be useful,
|    but WITHOUT ANY WARRANTY; without even the implied warranty of
|    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
|    GNU General Public License for more details.
|
|    You should have received a copy of the GNU General Public License
|    along with this program.  If not, see <http://www.gnu.org/licenses/>.
|
\**************************************************************************/

/* USE_SERIALIZATION
 * Necessary for extra verification of M-bitrelations
 * Warning: using an incompatible Boost version may cause exceptions during serialization
 * Build using boost version 1.43.0
 */
//#define USE_SERIALIZATION 
/* CPUPERFORMANCE
 * Enable measuring of cpu time spent in each function for manual optimization purposes
 */
//#define CPUPERFORMANCE
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stdexcept>
#define SHA1DETAIL_INLINE_IMPL
#include <hashclash/sha1detail.hpp>
#ifdef USE_SERIALIZATION
#include <map>
#include <fstream>
#include <hashclash/sha1differentialpath.hpp>
#include <hashclash/booleanfunction.hpp>
#include <hashclash/bestof.hpp>
#include <hashclash/progress_display.hpp>
#include <hashclash/sha1messagespace.hpp>
#include <hashclash/saveload.hpp>
#endif
#include <hashclash/rng.hpp>
#include <hashclash/timer.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/program_options.hpp>

using namespace std;
using namespace hashclash;
namespace po = boost::program_options;

#ifdef CPUPERFORMANCE
#include <hashclash/cpuperformance.hpp>
uint64 cpu_step_t[80];
#define UPDATE(s) update_performance_counter __update(cpu_step_t[s]);
#ifdef __GNUC__
#include <sched.h>
#endif
#else
#define UPDATE(s)
#endif

const int offset = 4;
uint32 firstmsg[16];
uint32 m[80];
uint32 m2[80];
uint32 Q[85];
uint32 Q2[85];
uint32 Qr30[85];
uint32 Q2r30[85];
uint32 metset1precomp[16][16];

#define MAX_LOOP_SIZE 22

uint64 tendcount = 0;
uint32 m_diff[80] = { 201326594, 3221225488, 3019898908, 1006632964, 3154116634, 536870928, 603979804, 3959422996, 201326594, 3221225488, 3019898908, 738197508, 3154116632, 2952790032, 12, 3087007760, 134217752, 2013265936, 134217748, 1879048208, 3087007772, 3892314112, 2952790020, 1476395024, 2952790028, 1207959552, 2952790016, 3087007760, 2550136848, 2684354560, 0, 0, 536870912, 2147483648, 16, 0, 536870928, 536870912, 16, 1610612736, 24, 3758096384, 2415919104, 805306384, 2952790016, 536870912, 536870912, 2684354560, 16, 2147483648, 536870912, 536870912, 536870912, 2147483648, 16, 0, 536870928, 2684354560, 0, 536870912, 536870912, 0, 0, 0, 0, 0, 0, 1, 32, 1, 1073741826, 1073741889, 1073741858, 2147483653, 3221225602, 3221225542, 1073741899, 2147483911, 137, 20};
const uint32 dQ[85] = { 0, 0, 0, 0, 0, 201326594, 3221225522, 2952791598, 3221225410, 3221225554, 3489660914, 2147483648, 4026531840, 3758096384, 0, 3758096384, 3221225472, 2147483648, 3758096384, 2147483648, 1073741824, 2147483648, 2684354560, 2147483648, 536870912, 0, 536870912, 2147483648, 3758096384, 0, 0, 2147483648, 2147483648, 0, 0, 0, 0, 0, 2147483648, 0, 2147483648, 0, 2147483648, 0, 1073741824, 0, 0, 2147483648, 0, 0, 0, 0, 2147483648, 0, 0, 0, 0, 0, 2147483648, 0, 2147483648, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2, 4294967295, 0, 4, 2, 2, 8, 4, 0, 4294967282};
const uint32 Qvaluemask[85] = { 0, 0, 0, 268435976, 1409620809, 1610612683, 3355443195, 1442840575, 1174405099, 1140851679, 1342179318, 3288334836, 3019899004, 603980664, 2348810465, 671088945, 3355447418, 2550138130, 805306642, 2818572355, 3892314114, 2415919106, 2952790016, 2818572288, 2818572288, 2818572288, 671088640, 2818572289, 3892314112, 2013265920, 402653184, 2147483648, 2684354560, 2147483648, 536870912, 0, 0, 0, 2147483648, 2684354560, 2684354560, 2684354560, 2684354560, 2684354561, 1610612736, 1342177280, 268435458, 2147483648, 2684354560, 536870912, 0, 2, 2147483648, 2684354560, 536870912, 0, 0, 2, 2147483648, 2684354562, 2684354560, 2684354560, 536870912, 0, 0, 0, 0, 0, 0, 0, 0, 4, 1, 1073741825, 1073741832, 6, 1, 1073741873, 1073741836, 7, 35, 24, 6, 0, 18};
const uint32 Qvaluemask_adj[85] = { 0, 0, 0, 268435976, 1409620809, 1610612683, 3355443195, 1442840575, 1174405099, 1140851679, 1342179318, 3288334836, 3019899004, 603980664, 2348810465, 671088945, 3355447418, 2550138130, 805306642, 2818572355, 3892314114, 2415919106, 2952790016, 2818572288, 2818572288, 2818572288, 671088640, 2818572289, 3892314112, 2013265920, 402653184, 2147483648, 2684354560, 2147483648, 536870912, 0, 0, 0, 2147483648, 2684354560, 2684354560, 2684354560, 2684354560, 2684354561, 1610612736, 1342177280, 268435458, 2147483648, 2684354560, 536870912, 0, 2, 2147483648, 2684354560, 536870912, 0, 0, 2, 2147483648, 2684354562, 2684354560, 2684354560, 536870912, 0, 0, 0, 0, 0, 0, 0, 0, 4, 1, 1073741825, 1073741832, 6, 1, 1073741873, 1073741836, 7, 35, 24, 6, 0, 18};
const uint32 Qvalue[85] = { 0, 0, 0, 268435968, 67174985, 67377672, 3288334296, 1375727986, 1157625865, 1073742216, 1073742224, 3288334336, 3019898884, 536871032, 1, 671088640, 1207959666, 134217728, 805306386, 134217728, 1073741826, 268435458, 2147483648, 2147483648, 0, 0, 0, 2147483649, 3355443200, 939524096, 134217728, 2147483648, 2684354560, 2147483648, 0, 0, 0, 0, 0, 2684354560, 0, 536870912, 2684354560, 536870913, 536870912, 1342177280, 2, 0, 536870912, 536870912, 0, 2, 0, 2684354560, 0, 0, 0, 2, 0, 536870914, 2684354560, 2684354560, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1073741824, 4, 1, 49, 1073741828, 5, 1, 16, 0, 0, 16};
const uint32 Qprev[85] = { 0, 0, 0, 0, 1073741824, 200991744, 0, 0, 0, 0, 1024, 0, 0, 768, 2147483648, 256, 4098, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 8, 4, 0, 48, 0, 0, 32, 16, 0, 0, 0};
const uint32 Qprev2[85] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 134217728, 0, 134217728, 0, 134217728, 0, 402653184, 0, 0, 536870912, 0, 0, 0, 0, 0, 0, 536870912, 0, 536870912, 0, 536870912, 0, 268435456, 0, 0, 536870912, 0, 0, 0, 0, 536870912, 0, 0, 0, 0, 0, 536870912, 0, 536870912, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1073741824, 0, 0, 0, 1073741824, 0, 0, 0, 0, 0, 0, 0};
const uint32 dF[80] = { 0, 0, 67108866, 3288283664, 1946159120, 1828713930, 738197918, 2952789616, 1946157076, 3489660928, 3758096384, 4227858432, 0, 939524096, 2147483648, 0, 2550136832, 2013265920, 2415919104, 268435456, 2281701376, 671088640, 3892314112, 671088640, 2281701376, 939524096, 3892314112, 4160749568, 2147483648, 2684354560, 0, 536870912, 0, 0, 0, 2147483648, 3758096384, 1610612736, 3758096384, 1610612736, 3758096384, 536870912, 268435456, 268435456, 2147483648, 536870912, 536870912, 0, 0, 2147483648, 536870912, 536870912, 0, 0, 0, 2147483648, 536870912, 2684354560, 3758096384, 3758096384, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1073741824, 3221225472, 2, 2147483649, 1073741824, 3221225468, 1, 2147483647, 8, 2147483646};

#ifdef USE_SERIALIZATION
// all M-bitrelations (including tunnel M-bitrelations)
// saved in BOOST_1_43_0 serialization string, use compatible BOOST version to load
// only used for verification purposes: verify_block()
vector< vector< vector<uint32> > > pathbitrelationsmatrix;
char pathbitrelationsmatrixstring[] = "22 serialization::archive 7 0 0 16 0 0 0 32 0 0 0 17 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 67108864 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 134217728 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 268435456 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 0 0 32 0 0 0 0 0 0 0 0 0 17 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 4096 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 134217728 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 1073741824 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 32 0 0 0 0 0 17 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 67108864 0 0 0 0 0 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 134217728 0 0 0 0 0 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 268435456 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 536870912 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 32 0 0 0 0 0 17 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 67108864 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 134217728 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 268435456 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 536870912 0 0 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 32 0 0 0 17 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 64 2048 64 2048 0 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 67108864 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 134217728 0 0 0 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 268435456 0 0 0 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 536870912 0 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 32 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 134217728 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 17 0 0 0 0 0 0 536870912 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 32 0 0 0 0 0 17 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 1024 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 67108864 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 134217728 0 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 268435456 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 536870912 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 32 0 0 0 0 0 17 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 17 0 0 8 0 8 0 0 0 8 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 1024 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 2048 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 4096 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 8192 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 67108864 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 134217728 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 268435456 0 268435456 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 536870912 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 1073741824 0 0 0 0 0 0 0 0 0 0 0 32 0 0 0 17 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 67108864 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 134217728 0 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 268435456 0 0 0 0 0 0 0 4294967295 0 0 0 0 0 0 32 0 0 0 0 0 17 0 0 4 0 0 0 0 0 0 0 4 0 0 0 0 0 0 4294967295 17 0 0 8 0 8 0 0 0 0 0 8 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 16 0 0 0 0 0 0 4294967295 0 0 17 0 0 0 0 0 0 0 0 0 0 64 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 128 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 134217728 0 0 0 0 0 0 4294967295 17 0 0 268435456 0 0 0 0 0 0 0 268435456 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 536870912 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 1073741824 0 0 0 0 0 0 0 0 0 32 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 2048 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 4096 0 0 0 0 0 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 67108864 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 134217728 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 268435456 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 536870912 0 0 0 0 0 0 0 0 0 0 32 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 17 0 0 0 0 8 0 8 0 0 0 0 0 8 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 16 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 32 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 64 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 128 0 0 0 0 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 67108864 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 134217728 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 268435456 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 536870912 0 0 0 0 4294967295 0 0 0 0 32 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 1024 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 2048 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 67108864 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 134217728 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 268435456 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 536870912 0 0 0 0 0 0 17 0 1073741824 1 1 0 1073741829 1073741825 1 0 3221225476 1 1073741824 0 2147483650 0 0 0 0 32 0 0 0 17 0 8 0 2 8 0 268435468 0 0 8 0 0 0 0 2 0 0 4294967295 17 0 4 0 0 0 0 0 0 0 4 0 0 0 0 4 0 0 4294967295 17 0 8 0 0 0 0 0 0 0 8 0 0 0 0 8 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 0 0 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 32768 0 0 4294967295 0 0 17 0 1080956941 888266766 3238303744 30003210 19038209 3238735880 3236978689 17072128 1654290440 2195628034 1128693760 2174808065 1120501764 202752 0 0 4294967295 17 0 2201829388 887160846 3246473216 33259530 3229351936 36864008 1110769664 2150367233 1130905612 2278490114 3273392130 2167439361 1075052549 344065 0 0 4294967295 17 0 2739996672 399777862 1133086721 58101826 33030144 2449055745 3259801600 2154463232 20776964 95903747 1106812928 40906753 1076887553 546817 0 0 4294967295 17 0 11091980 938541067 2178236417 1136885771 3283877889 3248128008 6619138 49020928 1621901324 2151612419 1121714177 2159575041 22282245 1130497 0 0 0 17 0 3254272004 346357770 2159296513 28672003 2156658689 1352171525 1109458947 2174484481 3224977408 2243100674 1114374147 2148696065 1128529921 2113537 0 0 4294967295 17 0 4194304 83886080 4194304 25165824 0 8388608 16777216 0 20971520 50331648 0 41943040 0 4194304 0 0 4294967295 17 0 8388608 33554432 8388608 50331648 0 16777216 33554432 0 41943040 100663296 0 16777216 0 8388608 0 0 4294967295 17 0 3780708353 393486405 100352 63344705 7864320 3236536321 3261898755 2213183488 3272935424 131555328 3229130752 35663872 1085276167 16799745 0 0 0 17 0 33554432 0 33554432 0 0 67108864 0 0 33554432 0 0 0 0 33554432 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 67108864 0 0 0 17 0 0 0 0 0 0 268435456 0 0 0 0 0 0 0 134217728 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 268435456 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 536870912 0 0 0 0 0 17 0 2147483648 2 2147483648 3 4 1 2 0 2147483648 2 0 1 4 2147483648 0 0 0 32 0 17 0 0 1 0 1 0 0 2 0 0 1 0 0 2 0 1 0 0 17 0 0 2 0 2 4 0 0 0 0 2 0 0 4 0 2 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 32 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 64 0 0 0 0 0 0 0 0 0 0 17 0 1132073476 603775050 3253916160 1083368514 3284422656 2169132036 1115543553 30588929 2700409344 2153410562 58662915 2176734209 389126 513 2048 0 0 17 0 596957189 377544712 3284342787 62799874 51109893 1134931972 3228385280 2213068803 3809261572 2230710273 3265150979 1106800643 40968194 1073764353 4096 0 4294967295 17 0 1102725121 627122180 25477123 5480451 1096204292 2149220352 54870019 2183954434 3787276288 40345600 2199224320 3249569795 30228480 16385 8192 0 4294967295 17 0 3262988296 272187393 48513024 1089454088 2198437888 2252242957 65896449 2190278657 1622425612 5652481 1127153666 31227904 1095139334 81920 16384 0 0 17 0 2737913868 60915727 3230089216 37421067 3285647365 347242505 1135869954 2200829952 1651261448 2242740226 3225026560 2207285249 40960005 81921 32768 0 4294967295 17 0 3806140417 661446656 1131649026 1115869187 2175041536 1119694849 6184963 34635778 555055108 19898369 1113227265 3245273091 28540930 6145 65536 0 0 17 0 1652099080 926294087 1074366465 1134858314 1104412672 382312460 2150146049 14843905 2689927176 110977026 1138794498 33566721 2359301 22529 131072 0 0 17 0 2174238725 379650057 3229892608 61964288 2178154497 345538565 1109983232 2173435905 1654788 2259091457 3277586435 2165473280 1080819719 16385 262144 0 0 17 0 1082130433 17301507 1075838977 25690115 45088768 1082130432 17825795 2097152 3238002692 86507523 2187329536 8388609 38797318 0 524288 0 4294967295 17 0 2209955852 882966542 3229958144 28540938 3252420608 112885768 1107623936 2175533057 1090273292 2259615746 3239837698 2165866497 1089732613 81921 1048576 0 0 17 0 551569420 837099592 2168768513 21303368 3255042048 2538807305 2181668864 42369025 1089030152 2206752769 2149883906 2184753152 27525124 71680 2097152 0 4294967295 17 0 45694988 921763855 2177187841 1122205707 3241934853 3283779592 10813442 15466496 1660698636 2243887107 1121714177 2149089281 47448065 81921 4194304 0 4294967295 17 0 0 8388612 33554432 8388608 50331652 0 16777216 33554432 0 41943040 33554432 0 16777220 0 8388608 0 4294967295 17 0 0 16777216 0 16777216 33554432 0 33554432 0 0 83886080 0 0 33554432 0 16777216 0 0 17 0 0 33554432 0 33554432 0 0 0 0 0 33554432 0 0 0 0 33554432 0 0 17 0 0 67108864 0 0 0 0 0 0 0 67108864 0 0 0 0 67108864 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 134217728 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 268435456 0 4294967295 17 0 0 536870912 0 0 0 0 0 0 0 0 0 0 0 0 536870912 0 0 17 0 3221225473 3 1073741825 3 0 3221225472 2147483651 2147483648 1073741829 3 2147483649 1 1073741828 0 1073741824 0 0 17 0 0 536870914 1073741824 3 5 0 1073741827 1 536870917 2 3221225474 1073741825 1073741824 0 2147483648 0 0 32 0 17 0 0 0 3 0 1 2 0 2 4 0 1 0 0 0 0 1 0 17 0 0 0 2 0 0 0 0 0 0 0 2 0 0 0 0 2 4294967295 17 0 30949376 103088130 3264495617 1131773954 42729477 3570958336 1117847552 60555265 2694397952 2217934850 7077888 2169667584 1094975491 16384 0 4 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2048 4294967295 0 0 17 0 1092884488 857464835 15382528 1086672907 1139056645 1376120845 3273285635 58769409 575207437 100835331 2213683202 52260865 1082884098 22529 0 8192 4294967295 17 0 3820666884 650313739 2173075457 57901058 2193113092 1345847300 1127153665 2156691456 3780165636 2269446146 1081950209 2167439361 19398657 16385 0 16384 0 17 0 549781513 298582022 36012032 786443 1080590340 29425676 52166658 35717121 1670578188 116129795 2260995 12845057 1087897602 0 0 32768 4294967295 17 0 2204780556 106766408 3247425536 1132269640 3222601728 1188110344 3228672000 2185527297 1137657868 2196791296 31563779 2175840256 22282240 71680 0 65536 0 17 0 3272867848 657457157 9830400 1076887560 1101135876 2265186317 1081081857 2156134401 2722889740 61865985 9043970 51380224 1130364928 0 0 131072 0 17 0 2157002761 13697026 1105805313 1120108555 2214068224 3249700877 12910594 2162425857 2724478984 60751874 3234332674 37257217 1116995584 81920 0 262144 4294967295 17 0 1122582541 846266376 3265085440 1113817096 3258187777 2208989192 31784961 66846720 2748071944 2185166848 3287547905 2153283584 30670851 81921 0 524288 4294967295 17 0 2210463753 554958854 1122041857 1079377931 1126170628 3544317965 1090781186 2186280961 1610940424 88866818 2178940930 30015489 1108344838 65536 0 1048576 0 17 0 3238809601 589086790 1090670594 33603648 61243393 316411905 2159132673 60948482 2188980224 124698626 19013633 3255582722 34439174 0 0 2097152 0 17 0 1115684865 100663299 1119879169 33554435 4194304 1350565888 33554435 8388608 3246391300 100663299 2168455168 33554433 6 0 0 4194304 0 17 0 2209955852 850460686 3242541056 44269578 3225157632 381321224 1076166656 2162950145 1107050508 2164195330 3277586434 2149089281 1079246853 81921 0 8388608 4294967295 17 0 1625311245 633675851 3267676160 56954955 3250847744 3344113673 2185863171 425985 2196326412 2267570178 10788866 2151198721 14942210 71680 0 16777216 0 17 0 0 0 33554432 0 33554432 67108864 0 0 0 0 33554432 0 0 0 0 33554432 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 67108864 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 134217728 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 268435456 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 536870912 4294967295 17 0 1130430468 815005710 2186346498 1104543747 1110441984 1398931461 1115947009 40894464 40173568 13369347 1102053378 21626883 17825796 65537 0 1073741824 4294967295 17 0 1 0 2147483649 0 2147483648 1 0 1 1 0 2147483650 0 0 0 0 2147483648 0";
// base M-bitrelations (excluding tunnel M-bitrelations)
// saved in BOOST_1_43_0 serialization string, use compatible BOOST version to load
// only used for verification purposes: check40();
vector< vector< vector<uint32> > > pathbitrelationsmatrix_base;
char pathbitrelationsmatrixstring_base[] = "22 serialization::archive 7 0 0 16 0 0 0 32 0 0 0 17 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 67108864 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 134217728 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 268435456 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 0 0 32 0 0 0 0 0 0 0 0 0 17 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 134217728 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 1073741824 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 32 0 0 0 0 0 17 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 67108864 0 0 0 0 0 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 134217728 0 0 0 0 0 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 268435456 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 536870912 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 32 0 0 0 0 0 17 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 67108864 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 134217728 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 268435456 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 536870912 0 0 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 32 0 0 0 17 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 67108864 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 134217728 0 0 0 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 268435456 0 0 0 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 536870912 0 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 32 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 134217728 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 17 0 0 0 0 0 0 536870912 0 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 32 0 0 0 0 0 17 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 67108864 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 134217728 0 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 268435456 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 536870912 0 0 0 0 0 0 0 0 0 4294967295 0 0 0 0 32 0 0 0 0 0 17 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 17 0 0 8 0 8 0 0 0 8 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 67108864 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 134217728 0 0 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 268435456 0 268435456 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 536870912 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 1073741824 0 0 0 0 0 0 0 0 0 0 0 32 0 0 0 17 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 67108864 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 134217728 0 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 268435456 0 0 0 0 0 0 0 4294967295 0 0 0 0 0 0 32 0 0 0 0 0 17 0 0 4 0 0 0 0 0 0 0 4 0 0 0 0 0 0 4294967295 17 0 0 8 0 8 0 0 0 0 0 8 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 16 0 0 0 0 0 0 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 134217728 0 0 0 0 0 0 4294967295 17 0 0 268435456 0 0 0 0 0 0 0 268435456 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 536870912 0 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 1073741824 0 0 0 0 0 0 0 0 0 32 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 67108864 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 134217728 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 268435456 0 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 536870912 0 0 0 0 0 0 0 0 0 0 32 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 17 0 0 0 0 8 0 8 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 67108864 0 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 134217728 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 268435456 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 536870912 0 0 0 0 4294967295 0 0 0 0 32 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 67108864 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 134217728 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 268435456 0 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 536870912 0 0 0 0 0 0 17 0 1073741824 1 1 0 1073741829 1073741825 1 0 3221225476 1 1073741824 0 2147483650 0 0 0 0 32 0 0 0 17 0 8 0 2 8 0 268435468 0 0 8 0 0 0 0 2 0 0 4294967295 17 0 4 0 0 0 0 0 0 0 4 0 0 0 0 4 0 0 4294967295 17 0 8 0 0 0 0 0 0 0 8 0 0 0 0 8 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 0 0 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 1080956941 888266766 3238303744 30003210 19038209 3238735880 3236978689 17072128 1654290440 2195628034 1128693760 2174808065 1120501764 202752 0 0 4294967295 17 0 2201829388 887160846 3246473216 33259530 3229351936 36864008 1110769664 2150367233 1130905612 2278490114 3273392130 2167439361 1075052549 344065 0 0 4294967295 0 0 17 0 11091980 938541067 2178236417 1136885771 3283877889 3248128008 6619138 49020928 1621901324 2151612419 1121714177 2159575041 22282245 1130497 0 0 0 17 0 3254272004 346357770 2159296513 28672003 2156658689 1352171525 1109458947 2174484481 3224977408 2243100674 1114374147 2148696065 1128529921 2113537 0 0 4294967295 17 0 4194304 83886080 4194304 25165824 0 8388608 16777216 0 20971520 50331648 0 41943040 0 4194304 0 0 4294967295 17 0 8388608 33554432 8388608 50331648 0 16777216 33554432 0 41943040 100663296 0 16777216 0 8388608 0 0 4294967295 17 0 1107820545 10485763 1132986369 11534339 25165824 1360003072 2097155 58720256 3257401348 39845891 2172649472 5242881 8388614 17301504 0 0 4294967295 17 0 33554432 0 33554432 0 0 67108864 0 0 33554432 0 0 0 0 33554432 0 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 67108864 0 0 0 17 0 0 0 0 0 0 268435456 0 0 0 0 0 0 0 134217728 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 268435456 0 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 536870912 0 0 0 0 0 17 0 2147483648 2 2147483648 3 4 1 2 0 2147483648 2 0 1 4 2147483648 0 0 0 32 0 17 0 0 1 0 1 0 0 2 0 0 1 0 0 2 0 1 0 0 17 0 0 2 0 2 4 0 0 0 0 2 0 0 4 0 2 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 0 3760921092 875085836 2189122049 1139045376 3258732544 280228869 2150725633 2176335873 2714366468 2246905857 1116176387 2211341312 1077276679 547328 2048 0 4294967295 17 0 596957189 377548808 3284342787 62799874 51109893 1134931972 3228385280 2213068803 3809261572 2230710273 3265150979 1106800643 40968194 1073797121 4096 0 4294967295 17 0 1102725121 627122180 25477123 5480451 1096204292 2149220352 54870019 2183954434 3787276288 40345600 2199224320 3249569795 30228480 16385 8192 0 4294967295 17 0 3262988296 272187393 48513024 1089454088 2198437888 2252242957 65896449 2190278657 1622425612 5652481 1127153666 31227904 1095139334 81920 16384 0 0 17 0 2737913868 60915727 3230089216 37421067 3285647365 347242505 1135869954 2200829952 1651261448 2242740226 3225026560 2207285249 40960005 81921 32768 0 4294967295 17 0 3806140417 661446656 1131649026 1115869187 2175041536 1119694849 6184963 34635778 555055108 19898369 1113227265 3245273091 28540930 6145 65536 0 0 17 0 3240624136 551682049 58720256 1087504392 1076625408 2268069901 1113849857 2156396545 2707947532 53084161 35127298 7340032 1075052548 524288 131072 0 4294967295 17 0 2174238725 379650057 3229892608 61964288 2178154497 345538565 1109983232 2173435905 1654788 2259091457 3277586435 2165473280 1080819719 16385 262144 0 0 17 0 1082130433 17301507 1075838977 25690115 45088768 1082130432 17825795 2097152 3238002692 86507523 2187329536 8388609 38797318 0 524288 0 4294967295 17 0 2209955852 882966542 3229958144 28540938 3252420608 112885768 1107623936 2175533057 1090273292 2259615746 3239837698 2165866497 1089732613 81921 1048576 0 0 17 0 2209431564 640745486 3268231168 36929546 3288072192 111837192 1078263808 2196504577 1104429068 2252275714 3252420610 2152235009 1100218373 606209 2097152 0 0 17 0 45694988 921763855 2177187841 1122205707 3241934853 3283779592 10813442 15466496 1660698636 2243887107 1121714177 2149089281 47448065 81921 4194304 0 4294967295 17 0 0 8388612 33554432 8388608 50331652 0 16777216 33554432 0 41943040 33554432 0 16777220 0 8388608 0 4294967295 17 0 0 16777216 0 16777216 33554432 0 33554432 0 0 83886080 0 0 33554432 0 16777216 0 0 17 0 0 33554432 0 33554432 0 0 0 0 0 33554432 0 0 0 0 33554432 0 0 17 0 0 67108864 0 0 0 0 0 0 0 67108864 0 0 0 0 67108864 0 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 134217728 0 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 268435456 0 4294967295 17 0 0 536870912 0 0 0 0 0 0 0 0 0 0 0 0 536870912 0 0 17 0 3221225473 3 1073741825 3 0 3221225472 2147483651 2147483648 1073741829 3 2147483649 1 1073741828 0 1073741824 0 0 17 0 0 536870914 1073741824 3 5 0 1073741827 1 536870917 2 3221225474 1073741825 1073741824 0 2147483648 0 0 32 0 17 0 0 0 3 0 1 2 0 2 4 0 1 0 0 0 0 1 0 17 0 0 0 2 0 0 0 0 0 0 0 2 0 0 0 0 2 4294967295 17 0 30949376 103088130 3264495617 1131773954 42729477 3570958336 1117847552 60555265 2694397952 2217934850 7077888 2169667584 1094975491 16384 0 4 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 4294967295 0 0 0 0 0 0 0 0 0 0 0 0 17 0 2739996672 399777798 1133084673 58101762 33032192 2449055745 3259801600 2154467328 20776964 95903747 1106814976 40906753 1076887553 546817 0 2048 4294967295 0 0 17 0 1092884488 857464835 15382528 1086672907 1139056645 1376120845 3273285635 58769409 575207437 100835331 2213683202 52260865 1082884098 22529 0 8192 4294967295 17 0 3820666884 650313739 2173075457 57901058 2193113092 1345847300 1127153665 2156691456 3780165636 2269446146 1081950209 2167439361 19398657 16385 0 16384 0 17 0 549781513 298582022 36012032 786443 1080590340 29425676 52166658 35717121 1670578188 116129795 2260995 12845057 1087897602 0 0 32768 4294967295 17 0 540753932 294191118 2181447681 1074495498 3253534720 3609755657 37552128 36569089 1123172360 2269577219 1075380227 2210430977 1097072641 606209 0 65536 4294967295 17 0 3272867848 657457157 9830400 1076887560 1101135876 2265186317 1081081857 2156134401 2722889740 61865985 9043970 51380224 1130364928 0 0 131072 0 17 0 2157002761 13697026 1105805313 1120108555 2214068224 3249700877 12910594 2162425857 2724478984 60751874 3234332674 37257217 1116995584 81920 0 262144 4294967295 17 0 1122582541 846266376 3265085440 1113817096 3258187777 2208989192 31784961 66846720 2748071944 2185166848 3287547905 2153283584 30670851 81921 0 524288 4294967295 17 0 2210463753 554958854 1122041857 1079377931 1126170628 3544317965 1090781186 2186280961 1610940424 88866818 2178940930 30015489 1108344838 65536 0 1048576 0 17 0 1650284545 885579776 42719235 24530946 39747585 2200285184 1123901441 2210955266 2202286084 47816705 1088061441 3229380611 1111326727 546817 0 2097152 4294967295 17 0 1115684865 100663299 1119879169 33554435 4194304 1350565888 33554435 8388608 3246391300 100663299 2168455168 33554433 6 0 0 4194304 0 17 0 2209955852 850460686 3242541056 44269578 3225157632 381321224 1076166656 2162950145 1107050508 2164195330 3277586434 2149089281 1079246853 81921 0 8388608 4294967295 17 0 3283173389 839974925 2169323521 1277961 3225157632 1454014472 1074069507 2154561537 2211725320 2191458305 1096548354 2185789440 1087635459 606209 0 16777216 4294967295 17 0 0 0 33554432 0 33554432 67108864 0 0 0 0 33554432 0 0 0 0 33554432 0 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 67108864 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 134217728 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 268435456 4294967295 17 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 536870912 4294967295 17 0 1130430468 815005710 2186346498 1104543747 1110441984 1398931461 1115947009 40894464 40173568 13369347 1102053378 21626883 17825796 65537 0 1073741824 4294967295 17 0 1 0 2147483649 0 2147483648 1 0 1 1 0 2147483650 0 0 0 0 2147483648 0";
#endif

uint32 Qtp1valsvec[30][1<<13];
uint32* Qtp1valsvecptr[30];
uint32 metpartialvec[30];

vector< vector<uint32> > target_dIHVs;

/***** Differential path over steps t=0,...,32 (w/o tunnels) *****/
/*
  Qt    | b31    Q-conditions            b0 | Delta mt (BSDR)
----------------------------------------------------------------------
Q-4:    |........ ........ ........ ........|
Q-3:    |........ ........ ........ ........|
Q-2:    |........ ........ ........ ........|
Q-1:    |...1.... ........ ........ ....0...|
Q0:     |.^.0.1.. .....0.1 ...00.10 .1..1..1|[!1,26,27!]
Q1:     |.0.+^-^^ ^^^^^1^0 ^^^11^10 .0..1.+0|[!-4,-30,+-31!]
Q2:     |1-...+-- -------- -------- --.-1.+0|[!-2,3,-4,-26,28,29,+-31!]
Q3:     |.-.-.0.1 11111111 11110++1 +-1-00-0|[!-2,26,27,28,-29!]
Q4:     |.-...1.0 11111111 1111-+++ ++0.1.+1|[!1,-3,4,26,-27,-28,-29,+-31!]
Q5:     |.-...0.. ........ ......0. .+.+10+0|[!-4,-29!]
Q6:     |.-.+.... ........ ......01 100-.0+.|[!2,3,4,26,-29!]
Q7:     |-1...1.. ........ ........ ...0.0..|[!2,4,-26,-27,29,30,+-31!]
Q8:     |1.1-.1.. ........ ........ .....1..|[!-1,26,-27!]
Q9:     |..-..0.. ........ ........ ........|[!-4,30,+-31!]
Q10:    |^...00.. ........ ........ .......1|[!-2,-3,4,-26,-28,29,+-31!]
Q11:    |..-.1... ........ ........ .......0|[!2,-26,27,-29!]
Q12:    |0-..1... ........ ........ ......!.|[!-3,4,-26,-27,-28,29,+-31!]
Q13:    |+..01... ........ ........ ........|[!-4,28,29,+-31!]
Q14:    |..-1.... ........ ........ ......!.|[!-2,3!]
Q15:    |+.0.1... ........ ........ ......!^|[!-4,-27,-28,-29,+-31!]
Q16:    |+-0.0... ........ ........ ......!.|[!3,-4,-27!]
Q17:    |+..1.... ........ ........ ......^.|[!-4,-27,-28,-29,30!]
Q18:    |-.+0.... ........ ........ ........|[!-2,4,-27!]
Q19:    |-...m... ........ ........ ........|[!4,28,29,-30!]
Q20:    |..+.r... ........ ........ ........|[!2,3,-4,-27,28,-29,+-31!]
Q21:    |^.r.m... ........ ........ ........|[!-27,29,30,+-31!]
Q22:    |..+.r... ........ ........ ........|[!-2,28,29,+-31!]
Q23:    |-...m... ........ ........ .......!|[!4,27,28,-30!]
Q24:    |.-+.R... ........ ........ ........|[!-2,3,28,-29,+-31!]
Q25:    |..r##... ........ ........ ........|[!27,-30!]
Q26:    |...rr... ........ ........ ........|[!-28,29,+-31!]
Q27:    |-....... ........ ........ ........|[!4,-27,28,29,+-31!] // alternative delta mt allowed
Q28:    |-.#..... ........ ........ ........|[!4,-27,28,+-31!]  // alternative delta mt allowed
Q29:    |........ ........ ........ ........|[!-29,+-31!]  // alternative delta mt allowed
Q30:    |..R..... ........ ........ ........|[!!]
conditions:
* 0, 1, +, -: self explanatory
* ^: Qt[b] == Qt-1[b]
* !: Qt[b] != Qt-1[b]
* r: Qt[b] == RL(Qt-1,30)[b]
* R: Qt[b] != RL(Qt-1,30)[b]
* m: Qt[b] == RL(Qt-2,30)[b]
* #: Qt[b] != RL(Qt-2,30)[b]
*/










bool dorapidsectionstatistics = false;
/***** MAIN FUNCTION *****/
void findfirstblock();
void build_target_dIHVs();
void sha1perf();

int maxruntime, statsinterval;

int main(int argc, char** argv) {
	std::string seedstr;
	bool dosha1bench = false;
	po::options_description desc("Allowed options");
	desc.add_options()
		("help,h"
			, "Show options.")
		("sha1benchmark,b"
			, po::bool_switch(&dosha1bench)
			, "Benchmark SHA-1 compression function.")
		("rapidsectionstats"
			, po::bool_switch(&dorapidsectionstatistics)
			, "More rapid statistics over 'indep.' sections")
		("seed"
			, po::value<string>(&seedstr)->default_value("")
			, "Specify seed")
		("maxruntime"
			, po::value<int>(&maxruntime)->default_value(-1)
			, "Maximum runtime in minutes")
		("statsinterval"
			, po::value<int>(&statsinterval)->default_value(5)
			, "Statistics interval in minutes")
		;
	po::variables_map vm;
	po::store(po::parse_command_line(argc, argv, desc), vm);
	po::notify(vm);
	if (vm.count("help")) {
		cout << desc << endl;
		cout << endl << "=== Help on statistics ===" << endl;
		cout << "'timeavg 40': #/s that steps t=[0,33) are ok." << endl;
		cout << "'avg 53 stats': success probability of steps t=[33,53)." << endl;
		cout << "'avg 61 stats': success probability of steps t=[53,61)." << endl;
		cout << "'avg 80 stats': success probability of steps t=[61,80)." << endl;
		return 0;
	}
	if (!seedstr.empty())
	{
		cout << "Using seed: " << seedstr << endl;
		seed(0);
		for (unsigned i = 0; i < seedstr.size(); ++i)
		{
			seed32_1 ^= seedstr[i];
			xrng128();
		}
	}
	if (maxruntime <= 0)
		maxruntime = -1;
	if (statsinterval <= 1)
		statsinterval = 1;
	if (dosha1bench) {
		sha1perf();
		return 0;
	}
	
#ifdef USE_SERIALIZATION
	{ stringstream tmp; tmp.str(string(pathbitrelationsmatrixstring)); boost::archive::text_iarchive ia(tmp); ia >> boost::serialization::make_nvp("pathbitrelationsmatrix", pathbitrelationsmatrix); }
	{ stringstream tmp; tmp.str(string(pathbitrelationsmatrixstring_base)); boost::archive::text_iarchive ia(tmp); ia >> boost::serialization::make_nvp("pathbitrelationsmatrix", pathbitrelationsmatrix_base); }
#if 0
	// show inside message relations that are not automatically taken into account by automatic program generation	
	for (unsigned t = 0; t < 16; ++t)
		for (unsigned b = 0; b < 32; ++b)
			if (pathbitrelationsmatrix[t][b].size()!=0 && pathbitrelationsmatrix[t][b][t] != 1<<b) {
				cout << "Inside message relation @ t=" << t << " b=" << b << ": ";
				for (unsigned b2 = 0; b2 < 32; ++b2)
					if (pathbitrelationsmatrix[t][b][t]&(1<<b2))
						cout << "(" << t << "," << b2 << ")";
				cout << endl;
			}
	// show free bits in steps t=14,15
	cout << "Free bits @ t=14: ";
	for (unsigned b = 0; b < 32; ++b)
		if (pathbitrelationsmatrix[14][b].size() == 0)
			cout << b << " ";
	cout << endl;
	cout << "Free bits @ t=15: ";
	for (unsigned b = 0; b < 32; ++b)
		if (pathbitrelationsmatrix[15][b].size() == 0)
			cout << b << " ";
	cout << endl;
	// show # base M-bitrelations (excluding tunnel M-bitrelations)
	unsigned basebitrels = 0;
	for (unsigned t = 0; t < 16; ++t)
		for (unsigned b = 0; b < 32; ++b)
			if (pathbitrelationsmatrix_base[t][b].size())
				++basebitrels;
	cout << "Base # of message bitrelations: " << basebitrels << endl;
#endif	
#endif // USE_SERIALIZATION

	// build sorted vector of the target dIHVs
	build_target_dIHVs();

	cout << "Starting collision search..." << endl;
	while (true) {
		try {
			findfirstblock();
		} catch (std::exception&e) { cerr << e.what() << endl; } catch (...) {}
	}
}
bool test_first_block(const uint32 block[16]) {
	static uint32 ihv[5];
	static uint32 me[80];
	memcpy(ihv, sha1_iv, 5*4); // or pick another IHV instead of default SHA-1 IV
	memcpy(me, block, 4*16);
	for (unsigned i = 16; i < 80; ++i)
		me[i]=rotate_left(me[i-3] ^ me[i-8] ^ me[i-14] ^ me[i-16], 1);
	sha1compress_me(ihv, me);
	Q2[0] = Q[0] = rotate_right(ihv[4], 30);
	Q2[1] = Q[1] = rotate_right(ihv[3], 30);
	Q2[2] = Q[2] = rotate_right(ihv[2], 30);
	Q2[3] = Q[3] = ihv[1];
	Q2[4] = Q[4] = ihv[0];
	if ((Q[0]&Qvaluemask_adj[0])!=Qvalue[0]) return false;
	if ((Q[1]&Qvaluemask_adj[1])!=(Qvalue[1]^(Q[0]&Qprev[1]))) return false;
	if ((Q[2]&Qvaluemask_adj[2])!=(Qvalue[2]^(Q[1]&Qprev[2])^(Q[0]&Qprev2[2]))) return false;
	if ((Q[3]&Qvaluemask_adj[3])!=(Qvalue[3]^(Q[2]&Qprev[3])^(Q[1]&Qprev2[3]))) return false;
	if ((Q[4]&Qvaluemask_adj[4])!=(Qvalue[4]^(Q[3]&Qprev[4])^(Q[2]&Qprev2[4]))) return false;
	return true;
}

bool step_0(); // this is where the actual near-collision attacks starts (in the second block)
uint64 fbcnt = 0;
void findfirstblock() {
	{UPDATE(79);
	while (true) {
		for (unsigned i = 0; i < 16; ++i)
			firstmsg[i] = xrng128();
		if (0==((++fbcnt)&0xFFFFF)) cout << "(fb:" << fbcnt << ")" << flush;
		if (test_first_block(firstmsg))
			break;
	}
	for (unsigned i = 0; i < 5; ++i) {
		Qr30[i] = rotate_left(Q[i], 30);
		Q2r30[i] = rotate_left(Q2[i], 30);
	}
	}//UPDATE(79);

	metset1precomp[0][0]=268435456;
	metset1precomp[0][1]=1073745936;
	metset1precomp[0][2]=201326612;
	metset1precomp[0][3]=536870916;
	metset1precomp[0][4]=939526152;
	metset1precomp[0][5]=671088656;
	metset1precomp[0][6]=671088640;
	metset1precomp[0][7]=201341960;
	metset1precomp[0][8]=402653186;
	metset1precomp[0][9]=671088668;
	metset1precomp[0][10]=469768204;
	metset1precomp[0][11]=603980016;
	metset1precomp[0][12]=469762056;
	metset1precomp[0][13]=49184798;
	metset1precomp[0][14]=350793780;
	metset1precomp[0][15]=2089592850;
 	step_0();
}
void build_target_dIHVs()
{
	target_dIHVs.clear();
	// base vector of 6 optimal dIHVs
        vector< vector<uint32> > base(6, vector<uint32>(5) );
        for (unsigned i = 0; i < 6; ++i) {
                base[i][0] = 1<<31;
                base[i][1] = 1<<1;
                base[i][2] = (i<2) ? (1<<31) : 0;
                base[i][3] = base[i][4] = 0;
                if (i==1 || i==4 || i==5) base[i][3] += 1<<4;
                if (i==0 || i==1) base[i][3] += 1<<6; else base[i][3] += 1<<7;
                if (i==0 || i==1) base[i][4] += (1<<11)+(1<<4)-(1<<2); else base[i][4] += (1<<12);
                if (i==1 || i==4 || i==5) base[i][4] += (1<<9);
                if (i==2 || i==4) base[i][4] += (1<<1)+(1<<3);
                if (i==3 || i==5) base[i][4] += (1<<4)-(1<<1);
        }
        // allow 6 extra messagebitfreedoms that each also give 6 optimal dIHVs
        // for second near-collision only specific single dIHV is targeted (the outcome of first near-collision)
        //    => loss of the 6 extra messagebitfreedoms, loss of factor 6 to target single dIHV instead of 6 dIHVs
        for (unsigned t794 = 0; t794 < 2; ++t794)
         for (unsigned t792 = 0; t792 < 2; ++t792)
          for (unsigned t787 = 0; t787 < 2; ++t787)
           for (unsigned t783 = 0; t783 < 2; ++t783)
            for (unsigned t763778 = 0; t763778 < 2; ++t763778)
             for (unsigned t771772 = 0; t771772 < 2; ++t771772)
             {
                for (unsigned i = 0; i < base.size(); ++i) {
                        vector<uint32> tmptmp = base[i];
                        if (t794) tmptmp[4] -= (1<<5);
                        if (t792) tmptmp[4] += (1<<3);
                        if (t787) { tmptmp[3] -= (1<<8); tmptmp[4] -= (1<<13); }
                        if (t783) { tmptmp[3] -= (1<<4); tmptmp[4] -= (1<<9); }
                        if (t763778) tmptmp[1] -= (1<<2);
                        if (t771772 && tmptmp[2]) { tmptmp[3] += (1<<7); tmptmp[4] += (1<<12); }
                        target_dIHVs.push_back(tmptmp);
                }
             }
	sort(target_dIHVs.begin(), target_dIHVs.end());
        cout << "# target dIHVs: " << target_dIHVs.size() << endl;
}
void sha1perf()
{
	uint32 ihv[5];
	uint32 msg[80];
	for (unsigned i = 0; i < 5; ++i)
		ihv[i] = xrng128();
	for (unsigned i = 0; i < 80; ++i)
		msg[i] = xrng128();
	uint64 totcnt = 0;
	cout << "Determining SHA1 performance (takes 10 minutes).\nDon't run any other processes." << endl;

	for (unsigned i = 0; i < (1<<23); ++i)
		sha1compress(ihv, msg);
	timer runtime(true);
	while (true) {
		for (unsigned i = 0; i < (1<<23); ++i)
			sha1compress(ihv, msg);
		totcnt += 1<<23;
		if (runtime.time() > 300)
			break;
	}
	cout << "SHA1 perf (w/ me)\t: 2^(" << log(double(totcnt)*3600.0/runtime.time())/log(2.0) << ") compressions per hour." << endl;

	for (unsigned i = 0; i < (1<<23); ++i)
		sha1compress_me(ihv, msg);
	totcnt = 0;
	runtime.start();
	while (true) {
		for (unsigned i = 0; i < (1<<23); ++i)
			sha1compress_me(ihv, msg);
		totcnt += 1<<23;
		if (runtime.time() > 300)
			break;
	}
	cout << "SHA1 perf (w/o me)\t: 2^(" << log(double(totcnt)*3600.0/runtime.time())/log(2.0) << ") compressions per hour." << endl;
}





/***** STATISTICS SECTION *****/
/* basic average statistics */
struct avg_data {
	uint64 avgcnt, avgsum;
	avg_data(): avgcnt(0), avgsum(0) {}
	void add_ok() { ++avgcnt; ++avgsum; }
	void add_bad() { ++avgcnt; }
	void add_cnt(uint64 toadd = 1) { avgcnt += toadd; }
	void add_sum(uint64 toadd = 1) { avgsum += toadd; }
	void show(const std::string& name) {
		double avg = double(avgsum)/double(avgcnt);
		double logavg = log(avg)/log(2.0);
		if (logavg >= 20 || logavg < -2.0) 
	                cout << name << ":	2^(" << logavg << ")";
		else
			cout << name << ":	" << avg;
		cout << "	(#=" << avgcnt << ", #ok=" << avgsum << ")" << endl;
	}
};
vector<avg_data> avg_data_vec(4000);

/* more extensive loop statistics: what is the probability for a certain succes percentage of a loop? */
struct loop_data {
        uint64 proc_cnt[101];
        uint64 totcnt;
        bool fulldetail;
        loop_data() { 
        	fulldetail = false;
                for (unsigned i = 0; i < 101; ++i)
                        proc_cnt[i] = 0;
                totcnt = 0;
        }
        void add(uint32 ok, uint32 cnt) {
                unsigned proc = floor(0.5 + (float(ok*100)/float(cnt)));
                if (proc > 100) throw;
                ++proc_cnt[proc];
                ++totcnt;
        }
        void add(unsigned proc) {
                if (proc > 100) throw;
                ++proc_cnt[proc];
                ++totcnt;
        }
        void show(const std::string& name) {
                cout << name << ": ";
                uint64 mincnt = totcnt >> 3;
                uint64 remcnt = totcnt;
                if (mincnt == 0) mincnt = 1;
                for (unsigned i = 0; i < 101; ++i)
                        if (proc_cnt[i] >= mincnt || i == 0 || i == 100 || (proc_cnt[i]>0 && fulldetail)) {
                                cout << "(" << i << "% occurs with p=" << double(proc_cnt[i])/double(totcnt) << ") ";
                                remcnt -= proc_cnt[i];
                        }
                cout << "(other p=" << double(remcnt)/double(totcnt) << ")" << endl;
        }
};
vector<loop_data> loop_data_vec(1024);

/* bit statistics over an array of uint32, see which bits have non-uniform distribution */
struct checkmaskcnt_type {
        void process(uint32* Qtbegin, uint32* Qtend, uint32 mask = 0xFFFFFFFF) {
                if (Qtend-Qtbegin < 2) return;
                bits.resize(32);
                for (unsigned b = 0; b < 32; ++b) {
			   if ((mask & (1<<b))==0) continue;
                        uint32 cnt = 0;
                        for (uint32* p = Qtbegin; p != Qtend; ++p)
                                if (*p & (1<<b))
                                        ++cnt;
                        bits[b].add(cnt, Qtend-Qtbegin);
                }
        }
        void show(const std::string& name) {
                if (bits.empty()) return;
                cout << name << ":" << endl;
                for (unsigned b = 0; b < 32; ++b) {
			   if (bits[b].totcnt == 0) continue;
                        bits[b].show("checkmaskbit " + boost::lexical_cast<string>(b));
                }
        }
        vector<loop_data> bits;
};
checkmaskcnt_type checkmaskcnt;
void process_checkmask(uint32* Qtbegin, uint32* Qtend, uint32 mask = 0xFFFFFFFF, uint32 add = 0)
{
	if (add) { for (uint32* ptr = Qtbegin; ptr != Qtend; ++ptr) *ptr += add; }
        checkmaskcnt.process(Qtbegin, Qtend,mask);
        if (add) { for (uint32* ptr = Qtbegin; ptr != Qtend; ++ptr) *ptr -= add; }
}

/* analyze which bits are affected by tunnel */
/* copy Q to Q2, change tunnel, recompute Q, call this function */
void tunnel_bitanalysis(unsigned Qtbegin, unsigned Qtend)
{
	for (unsigned t = Qtbegin; t < Qtend; ++t)
		for (unsigned b = 0; b < 32; ++b)
			if (b == 0 || b >= 27)
			{
				avg_data_vec[t*100+b].add_cnt(1);
				if ((Q2[offset+t]^Q[offset+t])&(1<<b))
					avg_data_vec[t*100+b].add_sum(1);
			}
}

vector<uint64> time_avg(1024,0);
vector<uint64> step_cnt(20,0);
timer spd_sw(true), runtime_sw(true), restart_sw(true), runtime_t40_sw(false);
#ifdef CPUPERFORMANCE
uint64 cpu_timestamp_begin = cpu_timestamp();
#endif
/* the main function that shows performance statistics every 15 secs */
/* also automatically restarts to step7 or step0 when step15 hasn't been reached yet */
void show_performance_data(const int correct_cpu_step_t = -1)
{
	// restart every 15 secs until time_avg[15] != 0
	if (time_avg[40]!=1 && restart_sw.time() < 15) 
		return;
	restart_sw.start();
	if (time_avg[15] == 0)
		throw std::runtime_error("restart");
	// show statistics every minute
	if (time_avg[40]!=1 && spd_sw.time() < 60*statsinterval) 
		return;
	spd_sw.start();

	UPDATE(78);
	cout << endl;
#ifdef CPUPERFORMANCE
	uint64 cputime = cpu_timestamp();
	uint64 cpuspend = cputime-cpu_timestamp_begin;
	if (correct_cpu_step_t != -1) {
		for (int t = 0; t <= correct_cpu_step_t; ++t)
			cpu_step_t[t] += cputime;
	}
	for (unsigned i = 0; i < 30; ++i)
		if (cpu_step_t[i]-cpu_step_t[i+1])
			cout << "t=" << i << "	" << floor(0.5 + (double(cpu_step_t[i]-cpu_step_t[i+1])*1000.0/double(cpuspend))) << "	" << cpu_step_t[i]-cpu_step_t[i+1] << endl;
     for (unsigned i = 30; i < 80; ++i) {
             if (cpu_step_t[i] > (cpuspend<<1))
                     cout << "i=" << i << "	" << floor(0.5 + (double(cpu_step_t[i]+cputime)*1000.0/double(cpuspend))) << "	" << (cpu_step_t[i]+cputime) << endl;
             else if (cpu_step_t[i])
                     cout << "i=" << i << "	" << floor(0.5 + (double(cpu_step_t[i])*1000.0/double(cpuspend))) << "	" << (cpu_step_t[i]) << endl;
     }
	if (correct_cpu_step_t != -1) {
		for (int t = 0; t <= correct_cpu_step_t; ++t)
			cpu_step_t[t] -= cputime;
	}
#endif
	for (unsigned i = 0; i < loop_data_vec.size(); ++i)
		if (loop_data_vec[i].totcnt)
			loop_data_vec[i].show("loop " + boost::lexical_cast<string>(i) + " stats");
	for (unsigned i = 0; i < avg_data_vec.size(); ++i)
		if (avg_data_vec[i].avgcnt)
			avg_data_vec[i].show("avg " + boost::lexical_cast<string>(i) + " stats");
	for (unsigned i = 0; i < time_avg.size(); ++i)
		if (time_avg[i] && i != 40)
			cout << "timeavg " << i << ": 	2^" << log(double(time_avg[i])/double(runtime_sw.time()))/log(2.0) << "#/s" << endl;
		else if (time_avg[i] && i == 40)
			cout << "timeavg " << i << ": 	2^" << log(double(time_avg[i])/double(runtime_t40_sw.time()))/log(2.0) << "#/s" << endl;
	for (unsigned i = 0; i < 20; ++i)
		if (step_cnt[i])
			cout << "(" << i << ":" << step_cnt[i] << ")	";
	cout << endl;
	checkmaskcnt.show("checkmask");
	
	if (maxruntime > 0 && runtime_sw.time() >= maxruntime*60)
	{
		cout << "Maximum runtime reached: aborting!" << endl;
		exit(0);
	}
}
/***** END STATISTICS SECTION *****/








// verify all Q-conditions and M-bitrelations
// !including! tunnel Q-conditions and M-bitrelations
// don't use after changing any tunnel
void verify_block(unsigned tend = 16, bool force = false)
{
	static uint32 cnt = 0;
	UPDATE(77);
	for (unsigned t = 16; t < tend; ++t)
		m[t]=rotate_left(m[t-3] ^ m[t-8] ^ m[t-14] ^ m[t-16], 1);
	for (unsigned t = 0; t < tend && t < 20; ++t)
		if (rotate_left(Q[offset+t-2],30)!=Qr30[offset+t-2]) {
			cout << "Precomp Qr30 error @ t=" << t << endl;
			exit(0);
		}
	for (unsigned t = 0; t < tend && t < 20; ++t) {
		bool terror = false;
		uint32 Qtp1 = m[t] + sha1_f1(Q[offset+t-1], rotate_left(Q[offset+t-2],30), rotate_left(Q[offset+t-3],30)) + sha1_ac[0] + rotate_left(Q[offset+t],5) + rotate_left(Q[offset+t-4],30);
		if (Qtp1 != Q[offset+t+1]) {
			cout << "Hash error @ t=" << t << ": " << hex << (Qtp1^Q[offset+t+1]) << dec << endl;
			terror = true;
		}   
		if ((Q[offset+t+1]^Qvalue[offset+t+1]^(Qprev[offset+t+1]&Q[offset+t])) & Qvaluemask[offset+t+1]) {
			cout << "Verify error @ t=" << t << ": ";
			cout << hex << ((Q[offset+t+1]^Qvalue[offset+t+1]^(Qprev[offset+t+1]&Q[offset+t])) & Qvaluemask[offset+t+1]) << dec << endl;
			terror = true;
		}
#ifdef USE_SERIALIZATION
		if (t < 16) {
			for (unsigned b = 0; b < 32; ++b)
				if (pathbitrelationsmatrix[t][b].size()) {
					uint32 r = pathbitrelationsmatrix[t][b][16]&1;
					for (unsigned j = 0; j <= t; ++j)
						r ^= m[j]&pathbitrelationsmatrix[t][b][j];
					if (hw(r)&1) {
 						cout << "Message relation error @ t=" << t << " b=" << b << ": ";
						for (unsigned j = 0; j <= t; ++j)
							for (unsigned b2 = 0; b2 < 32; ++b2)
								if (pathbitrelationsmatrix[t][b][j]&(1<<b2))
									cout << "(" << j << "," << b2 << ")";
						cout << endl;
						terror = true;
					}
				}
		}
#endif
		if (terror) exit(1);
	}
}

// verify computation t=0,...,32 and check if zero difference working state is actually achieved
void check40()
{
	UPDATE(40);
	for (int t = -4; t <= 0; ++t)
		Q2[offset+t] = Q[offset+t] + dQ[offset+t];
	for (int t = 0; t < 16; ++t) {
		uint32 Qtp1 = m[t] + sha1_f1(Q[offset+t-1], rotate_left(Q[offset+t-2],30), rotate_left(Q[offset+t-3],30))
			+ sha1_ac[0] + rotate_left(Q[offset+t],5) + rotate_left(Q[offset+t-4],30);
		if (Qtp1 != Q[offset+t+1]) {
			cerr << "check40(): Q error @ t=" << t << endl;
			exit(0);
		}
		m2[t] = m[t] ^ m_diff[t];
		Q2[offset+t+1] = m2[t] + sha1_f1(Q2[offset+t-1], rotate_left(Q2[offset+t-2],30), rotate_left(Q2[offset+t-3],30))
			+ sha1_ac[0] + rotate_left(Q2[offset+t],5) + rotate_left(Q2[offset+t-4],30);
		if (Q2[offset+t+1]-Q[offset+t+1] != dQ[offset+t+1]) {
			cerr << "check40(): dQ error @ t=" << t << endl;
			exit(0);
		}
	}
#ifdef USE_SERIALIZATION
	for (unsigned t = 0; t < 16; ++t) {
		for (unsigned b = 0; b < 32; ++b)
			if (pathbitrelationsmatrix_base[t][b].size()) {
				uint32 r = pathbitrelationsmatrix_base[t][b][16]&1;
				for (unsigned j = 0; j <= t; ++j)
					r ^= m[j]&pathbitrelationsmatrix_base[t][b][j];
				if (hw(r)&1) {
					cout << "Message relation error @ t=" << t << " b=" << b << ": ";
					for (unsigned j = 0; j <= t; ++j)
						for (unsigned b2 = 0; b2 < 32; ++b2)
							if (pathbitrelationsmatrix_base[t][b][j]&(1<<b2))
								cout << "(" << j << "," << b2 << ")";
					cout << endl;
					exit(0);
				}
			}
	}
#endif
	for (int t = 16; t < 20; ++t) {
		m[t]=rotate_left(m[t-3] ^ m[t-8] ^ m[t-14] ^ m[t-16], 1);
		m2[t] = m[t] ^ m_diff[t];
		Q[offset+t+1] = m[t] + sha1_f1(Q[offset+t-1], rotate_left(Q[offset+t-2],30), rotate_left(Q[offset+t-3],30))
			+ sha1_ac[0] + rotate_left(Q[offset+t],5) + rotate_left(Q[offset+t-4],30);
		Q2[offset+t+1] = m2[t] + sha1_f1(Q2[offset+t-1], rotate_left(Q2[offset+t-2],30), rotate_left(Q2[offset+t-3],30))
			+ sha1_ac[0] + rotate_left(Q2[offset+t],5) + rotate_left(Q2[offset+t-4],30);
 	}
	for (int t = 20; t < 33; ++t) {
		m[t]=rotate_left(m[t-3] ^ m[t-8] ^ m[t-14] ^ m[t-16], 1);
		m2[t] = m[t] ^ m_diff[t];
		Q[offset+t+1] = m[t] + sha1_f2(Q[offset+t-1], rotate_left(Q[offset+t-2],30), rotate_left(Q[offset+t-3],30))
			+ sha1_ac[1] + rotate_left(Q[offset+t],5) + rotate_left(Q[offset+t-4],30);
		Q2[offset+t+1] = m2[t] + sha1_f2(Q2[offset+t-1], rotate_left(Q2[offset+t-2],30), rotate_left(Q2[offset+t-3],30))
			+ sha1_ac[1] + rotate_left(Q2[offset+t],5) + rotate_left(Q2[offset+t-4],30);
	}
	if (Q2[offset+33]==Q[offset+33] && Q2[offset+32]==Q[offset+32] && Q2[offset+31]==Q[offset+31] && Q2[offset+30]==Q[offset+30] && Q2[offset+29]==Q[offset+29]) 
	{
#ifdef USE_SERIALIZATION
#if 0
	// this section saves all paths that get to this step
	// for probability and Q-conditions analysis
		sha1differentialpath path;
		for (int t = 16-4; t <= 33; ++t) {
			path[t] = sdr(Q[offset+t],Q2[offset+t]);
			if (t >= 16 && t < 33) {
				path.getme(t) = sdr(m[t],m2[t]);
				for (unsigned b = 0; b < 32; ++b) {
					bool bittm1active = path(t-1,b) == bc_minus || path(t-1,b) == bc_plus;
					bool bittm2active = path(t-2,(b+2)&31) == bc_minus || path(t-2,(b+2)&31) == bc_plus;
					bool bittm3active = path(t-3,(b+2)&31) == bc_minus || path(t-3,(b+2)&31) == bc_plus;
					unsigned acnt = 0;
					if (bittm1active) ++acnt;
					if (bittm2active) ++acnt;
					if (bittm3active) ++acnt;
					if (
						(t < 20 && (bittm1active || bittm2active || bittm3active))
					     || (t >= 20 && (acnt&1) && b < 31) // if two bits are active they cancel
					   ) 
					{ // there is a difference hence boolean function bitconditions are required
						if (path(t-1,b)==bc_constant) {
							if (Q[offset+t-1]&(1<<b)) path.setbitcondition(t-1,b,bc_one);
							else path.setbitcondition(t-1,b,bc_zero);
						}
						if (path(t-2,(b+2)&31)==bc_constant) {
							if (rotate_left(Q[offset+t-2],30)&(1<<b)) path.setbitcondition(t-2,(b+2)&31,bc_one);
							else path.setbitcondition(t-2,(b+2)&31,bc_zero);
						}
						if (path(t-3,(b+2)&31)==bc_constant) {
							if (rotate_left(Q[offset+t-3],30)&(1<<b)) path.setbitcondition(t-3,(b+2)&31,bc_one);
							else path.setbitcondition(t-3,(b+2)&31,bc_zero);
						}
					}
				}
			}
		}
		if (!test_path(path)) {
			show_path(path);
			exit(0);
		}

		static vector<sha1differentialpath> okpaths;
		okpaths.push_back(path);

		static timer save_sw(true);
		if (save_sw.time() > 600 || hw(uint32(okpaths.size()))==1) {
			static string okpathsfile;
			if (okpathsfile.size() == 0) {
				okpathsfile = "okpaths." + boost::lexical_cast<string>(getpid()) + ".";
				char hostname[256];
				if (0 == gethostname(hostname, 256))
					okpathsfile += string(hostname);
				else
					okpathsfile += string("hostname");
			}
			try {
				sort(okpaths.begin(), okpaths.end());
				save_bz2(okpaths, okpathsfile, text_archive);
			} catch (std::exception& e) {
				cout << "Failed to save OK paths in '" << okpathsfile << "':" << endl;
				cout << e.what() << endl;
			}
			save_sw.start();
		} // save_sw
#endif
#endif
		return;
	} else {
		cerr << "check40(): not really 40!" << endl;
		exit(0);
	}
}

template<int tstart, int tend>
inline void compute_mt() {
        for (int t = tstart; t < tend; ++t)
                m[t] = rotate_left(m[t-3] ^ m[t-8] ^ m[t-14] ^ m[t-16], 1);
}
template<int r> inline uint32 sha1_f(uint32 b, uint32 c, uint32 d);
template<> inline uint32 sha1_f<0>(uint32 b, uint32 c, uint32 d) { return sha1_f1(b,c,d) + 0x5A827999; }
template<> inline uint32 sha1_f<1>(uint32 b, uint32 c, uint32 d) { return sha1_f2(b,c,d) + 0x6ED9EBA1; }
template<> inline uint32 sha1_f<2>(uint32 b, uint32 c, uint32 d) { return sha1_f3(b,c,d) + 0x8F1BBCDC; }
template<> inline uint32 sha1_f<3>(uint32 b, uint32 c, uint32 d) { return sha1_f4(b,c,d) + 0xCA62C1D6; }
template<> inline uint32 sha1_f<4>(uint32 b, uint32 c, uint32 d) { cerr << "no 5th round!" << endl; exit(1); }

template<int tstart, int tend>
inline void compute_qt() {
        if (tstart >= tend) return;
        Qr30[offset+tstart-2] = rotate_left(Q[offset+tstart-2],30);
        uint32 a = Q[offset+tstart], b = Q[offset+tstart-1], c = Qr30[offset+tstart-2], d = Qr30[offset+tstart-3], e = Qr30[offset+tstart-4];
        e += rotate_left(a, 5) + sha1_f<(tstart+0)/20>(b,c,d) + m[tstart+0]; Q[offset+tstart+1] = e; 
        if (tstart+1 == tend) return;
        Qr30[offset+tstart-1] = b = rotate_left(b, 30);
        d += rotate_left(e, 5) + sha1_f<(tstart+1)/20>(a,b,c) + m[tstart+1]; Q[offset+tstart+2] = d; 
        if (tstart+2 == tend) return;
        Qr30[offset+tstart+0] = a = rotate_left(a, 30);
        c += rotate_left(d, 5) + sha1_f<(tstart+2)/20>(e,a,b) + m[tstart+2]; Q[offset+tstart+3] = c; 
        if (tstart+3 == tend) return;
        Qr30[offset+tstart+1] = e = rotate_left(e, 30);
        b += rotate_left(c, 5) + sha1_f<(tstart+3)/20>(d,e,a) + m[tstart+3]; Q[offset+tstart+4] = b; 
        if (tstart+4 == tend) return;
        Qr30[offset+tstart+2] = d = rotate_left(d, 30);
        a += rotate_left(b, 5) + sha1_f<(tstart+4)/20>(c,d,e) + m[tstart+4]; Q[offset+tstart+5] = a; 
        if (tstart+5 == tend) return;
        Qr30[offset+tstart+3] = c = rotate_left(c, 30);
        e += rotate_left(a, 5) + sha1_f<(tstart+5)/20>(b,c,d) + m[tstart+5]; Q[offset+tstart+6] = e; 
        if (tstart+6 == tend) return;
        Qr30[offset+tstart+4] = b = rotate_left(b, 30);
        d += rotate_left(e, 5) + sha1_f<(tstart+6)/20>(a,b,c) + m[tstart+6]; Q[offset+tstart+7] = d; 
        if (tstart+7 == tend) return;
        Qr30[offset+tstart+5] = a = rotate_left(a, 30);
        c += rotate_left(d, 5) + sha1_f<(tstart+7)/20>(e,a,b) + m[tstart+7]; Q[offset+tstart+8] = c; 
        if (tstart+8 == tend) return;
        Qr30[offset+tstart+6] = e = rotate_left(e, 30);
        b += rotate_left(c, 5) + sha1_f<(tstart+8)/20>(d,e,a) + m[tstart+8]; Q[offset+tstart+9] = b; 
        if (tstart+9 == tend) return;
        Qr30[offset+tstart+7] = d = rotate_left(d, 30);
        a += rotate_left(b, 5) + sha1_f<(tstart+9)/20>(c,d,e) + m[tstart+9]; Q[offset+tstart+10] = a; 
        if (tstart+10 == tend) return;
        Qr30[offset+tstart+8] = c = rotate_left(c, 30);
        e += rotate_left(a, 5) + sha1_f<(tstart+10)/20>(b,c,d) + m[tstart+10]; Q[offset+tstart+11] = e; 
        if (tstart+11 == tend) return;
        Qr30[offset+tstart+9] = b = rotate_left(b, 30);
        d += rotate_left(e, 5) + sha1_f<(tstart+11)/20>(a,b,c) + m[tstart+11]; Q[offset+tstart+12] = d; 
        if (tstart+12 == tend) return;
        Qr30[offset+tstart+10] = a = rotate_left(a, 30);
        c += rotate_left(d, 5) + sha1_f<(tstart+12)/20>(e,a,b) + m[tstart+12]; Q[offset+tstart+13] = c; 
        if (tstart+13 == tend) return;
        Qr30[offset+tstart+11] = e = rotate_left(e, 30);
        b += rotate_left(c, 5) + sha1_f<(tstart+13)/20>(d,e,a) + m[tstart+13]; Q[offset+tstart+14] = b; 
        if (tstart+14 == tend) return;
        Qr30[offset+tstart+12] = d = rotate_left(d, 30);
        a += rotate_left(b, 5) + sha1_f<(tstart+14)/20>(c,d,e) + m[tstart+14]; Q[offset+tstart+15] = a; 
        if (tstart+15 == tend) return;
        Qr30[offset+tstart+13] = c = rotate_left(c, 30);
        e += rotate_left(a, 5) + sha1_f<(tstart+15)/20>(b,c,d) + m[tstart+15]; Q[offset+tstart+16] = e; 
        if (tstart+16 == tend) return;
        Qr30[offset+tstart+14] = b = rotate_left(b, 30);
        d += rotate_left(e, 5) + sha1_f<(tstart+16)/20>(a,b,c) + m[tstart+16]; Q[offset+tstart+17] = d; 
        if (tstart+17 == tend) return;
        cerr << "compute_qt<" << tstart << "," << tend << ">(): t out of range!" << endl;
        exit(0); // prevent stupid mistake
}
template<int tstart, int tend>
inline void compute_qt2() {
        if (tstart >= tend) return;
        Q2r30[offset+tstart-2] = rotate_left(Q2[offset+tstart-2],30);
        uint32 a = Q2[offset+tstart], b = Q2[offset+tstart-1], c = Q2r30[offset+tstart-2], d = Q2r30[offset+tstart-3], e = Q2r30[offset+tstart-4];
        e += rotate_left(a, 5) + sha1_f<(tstart+0)/20>(b,c,d) + m2[tstart+0]; Q2[offset+tstart+1] = e; 
        if (tstart+1 == tend) return;
        Q2r30[offset+tstart-1] = b = rotate_left(b, 30);
        d += rotate_left(e, 5) + sha1_f<(tstart+1)/20>(a,b,c) + m2[tstart+1]; Q2[offset+tstart+2] = d; 
        if (tstart+2 == tend) return;
        Q2r30[offset+tstart+0] = a = rotate_left(a, 30);
        c += rotate_left(d, 5) + sha1_f<(tstart+2)/20>(e,a,b) + m2[tstart+2]; Q2[offset+tstart+3] = c; 
        if (tstart+3 == tend) return;
        Q2r30[offset+tstart+1] = e = rotate_left(e, 30);
        b += rotate_left(c, 5) + sha1_f<(tstart+3)/20>(d,e,a) + m2[tstart+3]; Q2[offset+tstart+4] = b; 
        if (tstart+4 == tend) return;
        Q2r30[offset+tstart+2] = d = rotate_left(d, 30);
        a += rotate_left(b, 5) + sha1_f<(tstart+4)/20>(c,d,e) + m2[tstart+4]; Q2[offset+tstart+5] = a; 
        if (tstart+5 == tend) return;
        Q2r30[offset+tstart+3] = c = rotate_left(c, 30);
        e += rotate_left(a, 5) + sha1_f<(tstart+5)/20>(b,c,d) + m2[tstart+5]; Q2[offset+tstart+6] = e; 
        if (tstart+6 == tend) return;
        Q2r30[offset+tstart+4] = b = rotate_left(b, 30);
        d += rotate_left(e, 5) + sha1_f<(tstart+6)/20>(a,b,c) + m2[tstart+6]; Q2[offset+tstart+7] = d; 
        if (tstart+7 == tend) return;
        Q2r30[offset+tstart+5] = a = rotate_left(a, 30);
        c += rotate_left(d, 5) + sha1_f<(tstart+7)/20>(e,a,b) + m2[tstart+7]; Q2[offset+tstart+8] = c; 
        if (tstart+8 == tend) return;
        Q2r30[offset+tstart+6] = e = rotate_left(e, 30);
        b += rotate_left(c, 5) + sha1_f<(tstart+8)/20>(d,e,a) + m2[tstart+8]; Q2[offset+tstart+9] = b; 
        if (tstart+9 == tend) return;
        Q2r30[offset+tstart+7] = d = rotate_left(d, 30);
        a += rotate_left(b, 5) + sha1_f<(tstart+9)/20>(c,d,e) + m2[tstart+9]; Q2[offset+tstart+10] = a; 
        if (tstart+10 == tend) return;
        Q2r30[offset+tstart+8] = c = rotate_left(c, 30);
        e += rotate_left(a, 5) + sha1_f<(tstart+10)/20>(b,c,d) + m2[tstart+10]; Q2[offset+tstart+11] = e; 
        if (tstart+11 == tend) return;
        Q2r30[offset+tstart+9] = b = rotate_left(b, 30);
        d += rotate_left(e, 5) + sha1_f<(tstart+11)/20>(a,b,c) + m2[tstart+11]; Q2[offset+tstart+12] = d; 
        if (tstart+12 == tend) return;
        Q2r30[offset+tstart+10] = a = rotate_left(a, 30);
        c += rotate_left(d, 5) + sha1_f<(tstart+12)/20>(e,a,b) + m2[tstart+12]; Q2[offset+tstart+13] = c; 
        if (tstart+13 == tend) return;
        Q2r30[offset+tstart+11] = e = rotate_left(e, 30);
        b += rotate_left(c, 5) + sha1_f<(tstart+13)/20>(d,e,a) + m2[tstart+13]; Q2[offset+tstart+14] = b; 
        if (tstart+14 == tend) return;
        Q2r30[offset+tstart+12] = d = rotate_left(d, 30);
        a += rotate_left(b, 5) + sha1_f<(tstart+14)/20>(c,d,e) + m2[tstart+14]; Q2[offset+tstart+15] = a; 
        if (tstart+15 == tend) return;
        Q2r30[offset+tstart+13] = c = rotate_left(c, 30);
        e += rotate_left(a, 5) + sha1_f<(tstart+15)/20>(b,c,d) + m2[tstart+15]; Q2[offset+tstart+16] = e; 
        if (tstart+16 == tend) return;
        Q2r30[offset+tstart+14] = b = rotate_left(b, 30);
        d += rotate_left(e, 5) + sha1_f<(tstart+16)/20>(a,b,c) + m2[tstart+16]; Q2[offset+tstart+17] = d; 
        if (tstart+17 == tend) return;
        cerr << "compute_qt2<" << tstart << "," << tend << ">(): t out of range!" << endl;
        exit(0); // prevent stupid mistake
}

template<int tstart, int tend>
void check_comp()
{
	for (unsigned i = tstart; i < tend; ++i) {
		Q2[offset+i+1] = Q[offset+i+1];
		Q2r30[offset+i-2] = Qr30[offset+i-2];
		Q2r30[offset+i-3] = Qr30[offset+i-3];
		Q2r30[offset+i-4] = Qr30[offset+i-4];
		m2[i] = m[i];
	}
	compute_mt<tstart,tend>();
	compute_qt<tstart,tend>();
	for (unsigned i = tstart; i < tend; ++i) {
		bool bad = false;
		if (Q2[offset+i+1]!=Q[offset+i+1]) { cerr << "Q[" << (i+1) << "]bad "; bad = true; }
		if (Q2r30[offset+i-2]!=Qr30[offset+i-2]) { cerr << "Qr30[" << (i-2) << "]bad "; bad = true; }
		if (Q2r30[offset+i-3]!=Qr30[offset+i-3]) { cerr << "Qr30[" << (i-3) << "]bad "; bad = true; }
		if (Q2r30[offset+i-4]!=Qr30[offset+i-4]) { cerr << "Qr30[" << (i-4) << "]bad "; bad = true; }
		if (m2[i] != m[i]) { cerr << "m[" << i << "]bad "; bad = true; }
		if (bad) { cout << endl; exit(0); }
	}
}

uint32 gQ19val;

/* check whether near-collision is achieved and maintain statistics about 'independent' sections */
void check_nc()
{
	UPDATE(53);
	bool t33ok = true;
#if 1
	//  to enable more rapid collecting of statistics
	if (!(Q2[offset+33]==Q[offset+33] && Q2[offset+32]==Q[offset+32] && Q2[offset+31]==Q[offset+31] && Q2[offset+30]==Q[offset+30] && Q2[offset+29]==Q[offset+29]))
		t33ok = false;
	// 'assume' zero difference is achieved for statistics of subsequent sections
	for (unsigned i = 33-4; i <= 33; ++i) {
		Q2[offset+i] = Q[offset+i];
		Q2r30[offset+i] = Qr30[offset+i];
	}
#endif
	compute_mt<33,80>();
	for (int t = 33; t < 80; ++t)
		m2[t] = m[t] ^ m_diff[t];
	// second section: t = [33,53)
	compute_qt<33,43>();
	compute_qt<43,53>();
	compute_qt2<33,43>();
	compute_qt2<43,53>();
	avg_data_vec[53].add_cnt(1);
	bool t53ok = false;
	if (Q2[offset+53]==Q[offset+53] && Q2[offset+52]==Q[offset+52] && Q2[offset+51]==Q[offset+51] && Q2[offset+50]==Q[offset+50] && Q2[offset+49]==Q[offset+49]) {
		avg_data_vec[53].add_sum(1);
		++time_avg[53];
		t53ok = true;
	} else {
		// return; 
		// 'assume' zero difference is achieved for statistics of subsequent sections
		for (unsigned i = 53-4; i <= 53; ++i) {
			Q2[offset+i] = Q[offset+i];
			Q2r30[offset+i] = Qr30[offset+i];
		}
	}
	// third section: t = [53,61)
	compute_qt<53,61>();
	compute_qt2<53,61>();
	bool t61ok = false;
	avg_data_vec[61].add_cnt(1);
	if (Q2[offset+61]==Q[offset+61] && Q2[offset+60]==Q[offset+60] && Q2[offset+59]==Q[offset+59] && Q2[offset+58]==Q[offset+58] && Q2[offset+57]==Q[offset+57]) {
		avg_data_vec[61].add_sum(1);
		if (t53ok) ++time_avg[61];
		t61ok = true;
	}  else {
		// return; 
		// 'assume' zero difference is achieved for statistics of subsequent section
		for (unsigned i = 61-4; i <= 61; ++i) {
			Q2[offset+i] = Q[offset+i];
			Q2r30[offset+i] = Qr30[offset+i];
		}
	}
	// fourth and final section: t = [61,80)
	compute_qt<61,70>();
	compute_qt<70,80>();
	compute_qt2<61,70>();
	compute_qt2<70,80>();
	static vector<uint32> dihv(5);
        dihv[0] = rotate_left(Q2[offset+80-4],30)-rotate_left(Q[offset+80-4],30);
        dihv[1] = rotate_left(Q2[offset+80-3],30)-rotate_left(Q[offset+80-3],30);
        dihv[2] = rotate_left(Q2[offset+80-2],30)-rotate_left(Q[offset+80-2],30);
        dihv[3] = Q2[offset+80-1]-Q[offset+80-1];
        dihv[4] = Q2[offset+80]-Q[offset+80];
	avg_data_vec[80].add_cnt(1);
	bool t80ok = false;
	if (binary_search(target_dIHVs.begin(), target_dIHVs.end(), dihv)) {
		t80ok = true;
		avg_data_vec[80].add_sum(1);
		if (t33ok && t53ok && t61ok) {
			++time_avg[80];
			cout << "blocks: " << endl;
			for (unsigned i = 0; i < 16; ++i)
				cout << firstmsg[i] << " ";
			cout << endl;
			for (unsigned i = 0; i < 16; ++i)
				cout << m[i] << " ";
			cout << endl;
			exit(0);
		}
	}
	if (t53ok && t61ok) avg_data_vec[90].add_ok(); else avg_data_vec[90].add_bad();
	if (t53ok && t80ok) avg_data_vec[91].add_ok(); else avg_data_vec[91].add_bad();
	if (t61ok && t80ok) avg_data_vec[92].add_ok(); else avg_data_vec[92].add_bad();
	if (t53ok && t61ok && t80ok) avg_data_vec[93].add_ok(); else avg_data_vec[93].add_bad();
}

void step_16_33()
{
	const unsigned updatet = 25;
	UPDATE(updatet);
#if 0
	// verify computation
	check_comp<16,25>()
	compute_mt<25,33>();
	compute_qt<25,33>();
	// determine probability of Q-conditions disturbed by (later) tunnels
	bool badcond = false;
	if ( (Q[offset+17]&((1<<31)|(1<<28)|(1<<1)))==((1<<28)^(1<<1)) ) avg_data_vec[17].add_bad(); else { badcond = true; avg_data_vec[17].add_ok(); }
	if ((Q[offset+18]&2952790016)==2147483648) avg_data_vec[18].add_bad(); else { badcond = true; avg_data_vec[18].add_ok(); }
	if ( (Q[offset+19]&((1<<31)|(1<<27))) == ((1<<31)^((Q[offset+17]>>2)&(1<<27))) ) avg_data_vec[19].add_bad(); else { badcond = true; avg_data_vec[19].add_ok(); }
	if ( (Q[offset+20]&((1<<29)|(1<<27))) == ((Q[offset+19]>>2)&(1<<27)) ) avg_data_vec[20].add_bad(); else { badcond = true; avg_data_vec[20].add_ok(); }
	if ( (Q[offset+21]&((1<<31)|(1<<29)|(1<<27))) == ((Q[offset+20]&((1<<31)|(1<<27)))^((Q[offset+20]>>2)&(1<<29))) ) avg_data_vec[21].add_bad(); else { badcond = true; avg_data_vec[21].add_ok(); }
	if (badcond) avg_data_vec[39].add_ok(); else avg_data_vec[39].add_bad();
#else
	compute_mt<25,33>();
	compute_qt<25,33>();
#endif
	for (int t = 16-4; t <= 16; ++t) {
		Q2[offset+t] = Q[offset+t] + dQ[offset+t];
		Q2r30[offset+t] = rotate_left(Q2[offset+t],30);
	}
	for (int t = 16; t < 33; ++t)
		m2[t] = m[t] ^ m_diff[t];
	compute_qt2<16,33>();
	avg_data_vec[40].add_cnt(1);
	if (Q2[offset+33]==Q[offset+33] && Q2[offset+32]==Q[offset+32] && Q2[offset+31]==Q[offset+31] && Q2[offset+30]==Q[offset+30] && Q2[offset+29]==Q[offset+29]) {
		if (time_avg[40] == 0) runtime_t40_sw.start();
		avg_data_vec[40].add_sum(1);
		++time_avg[40];
		show_performance_data(updatet);
#if 0
		static set< vector<uint32> > okmsg;
		static vector<uint32> msg(16);
		for (unsigned i = 0; i < 16; ++i) msg[i] = m[i];
		if (okmsg.find(msg) != okmsg.end()) { cout << "msg found twice ?!?!" << endl; exit(0); }
		okmsg.insert(msg);
#endif
//		check40();
		check_nc();

	} else {
		//  to enable more rapid collecting of statistics
		if (dorapidsectionstatistics)
			check_nc();
	}
}

void step_24_case01()
{
	UPDATE(24);
	compute_mt<24,25>();
	compute_qt<24,25>();
	if ( ((Q[offset+25]^(Q[offset+23]>>2))&(3<<27)) != (3<<27) ) return;
	step_16_33();
}
void step_24_case4()
{
	UPDATE(24);
	compute_mt<24,25>();
	compute_qt<24,25>();
	const uint32 Q25val = ((Q[offset+24]>>2)&(1<<29)) ^ ((Q[offset+23]>>2)&(1<<27)) ^ (1<<27);
	if ( (Q[offset+25]&((1<<29)|(1<<27))) != Q25val) return;
	step_16_33();
}
void step_23_case01()
{
	UPDATE(23);
	compute_mt<23,24>();
	compute_qt<23,24>();
	
	const uint32 Q24val = ((Q[offset+23]>>2)&(1<<27))^(1<<27);
	if ( (Q[offset+24]&((1<<27)|(1<<29))) == Q24val)// && (Q[offset+24]&(3<<30))!=0 )
		step_24_case01();

	Q[offset+7] += 1<<6; m[6] += 1<<6; m[7] -= 1<<11; m[11] -= 1<<4;
	compute_mt<19,24>();
	compute_qt<19,24>();
	if ( (Q[offset+24]&((1<<27)|(1<<29))) == Q24val)// && (Q[offset+24]&(3<<30))!=0 )
		step_24_case01();
	Q[offset+7] -= 1<<6; m[6] -= 1<<6; m[7] += 1<<11; m[11] += 1<<4;

	Q[offset+7] += 1<<8; m[6] += 1<<8; m[7] -= 1<<13; m[11] -= 1<<6;
	compute_mt<19,24>();
	compute_qt<19,24>();
	if ( (Q[offset+24]&((1<<27)|(1<<29))) == Q24val)// && (Q[offset+24]&(3<<30))!=0 )
		step_24_case01();
	Q[offset+7] -= 1<<8; m[6] -= 1<<8; m[7] += 1<<13; m[11] += 1<<6;

	Q[offset+7] += 5<<6; m[6] += 5<<6; m[7] -= 5<<11; m[11] -= 5<<4;
	compute_mt<19,24>();
	compute_qt<19,24>();
	if ( (Q[offset+24]&((1<<27)|(1<<29))) == Q24val)// && (Q[offset+24]&(3<<30))!=0 )
		step_24_case01();
	Q[offset+7] -= 5<<6; m[6] -= 5<<6; m[7] += 5<<11; m[11] += 5<<4;
}
void step_23_case4()
{
	UPDATE(23);
	compute_mt<23,24>();
	compute_qt<23,24>();
	
	const uint32 Q24val = ((Q[offset+23]>>2)&(3<<27))^(3<<27);
	if ( (Q[offset+24]&(3<<27)) == Q24val)// && (Q[offset+24]&(3<<29))!=0 )
		step_24_case4();

	Q[offset+7] += 1<<6; m[6] += 1<<6; m[7] -= 1<<11; m[11] -= 1<<4;
	compute_mt<19,24>();
	compute_qt<19,24>();
	if ( (Q[offset+24]&(3<<27)) == Q24val)// && (Q[offset+24]&(3<<29))!=0 )
		step_24_case4();
	Q[offset+7] -= 1<<6; m[6] -= 1<<6; m[7] += 1<<11; m[11] += 1<<4;

	Q[offset+7] += 1<<8; m[6] += 1<<8; m[7] -= 1<<13; m[11] -= 1<<6;
	compute_mt<19,24>();
	compute_qt<19,24>();
	if ( (Q[offset+24]&(3<<27)) == Q24val)// && (Q[offset+24]&(3<<29))!=0 )
		step_24_case4();
	Q[offset+7] -= 1<<8; m[6] -= 1<<8; m[7] += 1<<13; m[11] += 1<<6;

	Q[offset+7] += 5<<6; m[6] += 5<<6; m[7] -= 5<<11; m[11] -= 5<<4;
	compute_mt<19,24>();
	compute_qt<19,24>();
	if ( (Q[offset+24]&(3<<27)) == Q24val)// && (Q[offset+24]&(3<<29))!=0 )
		step_24_case4();
	Q[offset+7] -= 5<<6; m[6] -= 5<<6; m[7] += 5<<11; m[11] += 5<<4;
}

void step_22_case01()
{
	UPDATE(22);
	compute_mt<22,23>();
	compute_qt<22,23>();
	if ( (Q[offset+23]&((1<<31)|(1<<27)|(1<<0))) == ((1<<31)^(1<<0)^(Q[offset+22]&((1<<27)|(1<<0)))) )
		step_23_case01();
	Q[offset+7] += 1<<7; m[6] += 1<<7; m[7] -= 1<<12; m[11] -= 1<<5;
	if (m[14]&(1<<6)) {
		Q[offset+15] -= 1<<6; m[14] -= 1<<6; m[15] +=1<<11;
		compute_mt<16,23>();
		compute_qt<16,23>();
		if ( (Q[offset+23]&((1<<31)|(1<<27)|(1<<0))) == ((1<<31)^(1<<0)^(Q[offset+22]&((1<<27)|(1<<0)))) )
			step_23_case01();
		Q[offset+15] += 1<<6; m[14] += 1<<6; m[15] -=1<<11;
	} else {
		Q[offset+15] += 1<<6; m[14] += 1<<6; m[15] -=1<<11;
		compute_mt<16,23>();
		compute_qt<16,23>();
		if ( (Q[offset+23]&((1<<31)|(1<<27)|(1<<0))) == ((1<<31)^(1<<0)^(Q[offset+22]&((1<<27)|(1<<0)))) )
			step_23_case01();
		Q[offset+15] -= 1<<6; m[14] -= 1<<6; m[15] +=1<<11;
	}
	Q[offset+7] -= 1<<7; m[6] -= 1<<7; m[7] += 1<<12; m[11] += 1<<5;
}

void step_22_case4()
{
	UPDATE(22);
	compute_mt<22,23>();
	compute_qt<22,23>();
	const uint32 Q23val = ((1<<31)^((Q[offset+21]>>2)&(7<<27))) ;
	step_23_case4();
	Q[offset+7] += 1<<7; m[6] += 1<<7; m[7] -= 1<<12; m[11] -= 1<<5;
	if (m[14]&(1<<6)) {
		Q[offset+15] -= 1<<6; m[14] -= 1<<6; m[15] +=1<<11;
		compute_mt<16,23>();
		compute_qt<16,23>();
		step_23_case4();
		Q[offset+15] += 1<<6; m[14] += 1<<6; m[15] -=1<<11;
	} else {
		Q[offset+15] += 1<<6; m[14] += 1<<6; m[15] -=1<<11;
		compute_mt<16,23>();
		compute_qt<16,23>();
		step_23_case4();
		Q[offset+15] -= 1<<6; m[14] -= 1<<6; m[15] +=1<<11;
	}
	Q[offset+7] -= 1<<7; m[6] -= 1<<7; m[7] += 1<<12; m[11] += 1<<5;
}

void step_21b()
{
	UPDATE(21);
	compute_mt<21,22>();
	compute_qt<21,22>();
	const uint32 Q22val = (Q[offset+21]>>2) & (1<<27);
	const uint32 Q22val2 = Q22val ^ (3<<29);
	const uint32 Q22mask = (1<<27)|(1<<29);
	const uint32 Q22mask2 = (1<<27)|(7<<29);
	const uint32 Q22bu = Q[offset+22];
	if ( (Q[offset+22]&Q22mask)==Q22val) step_22_case01();
	else if ( (Q[offset+22]&Q22mask2)==Q22val2) step_22_case4();
	if ( ((Q22bu-(1<<29))&Q22mask)==Q22val || ((Q22bu-(1<<29))&Q22mask2)==Q22val2) {
		Q[offset+12] -= 1<<6; Qr30[offset+12] = rotate_left(Q[offset+12],30); m[11] -= 1<<6; m[12] += 1<<11;
		compute_mt<16,22>();
		compute_qt<16,22>();
		if ( (Q[offset+22]&Q22mask)==Q22val) step_22_case01();
		else if ( (Q[offset+22]&Q22mask2)==Q22val2) step_22_case4();
		Q[offset+12] += 1<<6; Qr30[offset+12] = rotate_left(Q[offset+12],30); m[11] += 1<<6; m[12] -= 1<<11;
	}

	if ((( (Q22bu + (1<<26) - ((m[17]&(1<<6))<<21)) & (1<<27)) ) != Q22val) return;
	Q[offset+10] += 1<<7; m[9] += 1<<7; m[10] -= 1<<12; m[14] -= 1<<5;
	compute_mt<16,22>();	
	compute_qt<16,22>();
	const uint32 Q22bu2 = Q[offset+22];
	if ( (Q[offset+22]&Q22mask)==Q22val) step_22_case01();
	else if ( (Q[offset+22]&Q22mask2)==Q22val2) step_22_case4();
	if ( ((Q22bu2-(1<<29))&Q22mask)==Q22val || ((Q22bu2-(1<<29))&Q22mask2)==Q22val2) {
		Q[offset+12] -= 1<<6; Qr30[offset+12] = rotate_left(Q[offset+12],30); m[11] -= 1<<6; m[12] += 1<<11;
		compute_mt<16,22>();
		compute_qt<16,22>();
		if ( (Q[offset+22]&Q22mask)==Q22val) step_22_case01();
		else if ( (Q[offset+22]&Q22mask2)==Q22val2) step_22_case4();
		Q[offset+12] += 1<<6; Qr30[offset+12] = rotate_left(Q[offset+12],30); m[11] += 1<<6; m[12] -= 1<<11;
	}
	Q[offset+10] -= 1<<7; m[9] -= 1<<7; m[10] += 1<<12; m[14] += 1<<5;
}
void step_21()
{
	UPDATE(20);
	step_21b();
	Q[offset+10] += 1<<6; Q[offset+15] += 1<<6;
	m[9] += 1<<6; m[10] -= 1<<11; m[14] += (1<<6) - (1<<4); m[15] -= 1<<11;
	compute_mt<16,21>();
	compute_qt<16,21>();
	step_21b();
	Q[offset+10] -= 1<<6; Q[offset+15] -= 1<<6;
	m[9] -= 1<<6; m[10] += 1<<11; m[14] -= (1<<6) - (1<<4); m[15] += 1<<11;
}

void step_19()
{
	UPDATE(19);
	compute_mt<19,21>();
	compute_qt<19,21>();
	if ((Q[offset+21]^(Q[offset+20]>>2))&(1<<29)) return;
	const uint32 Q20mask = (1<<29)|(1<<27)|(1<<31);
	const uint32 Q20val = ((Q[offset+19]>>2)&(1<<27))|(Q[offset+20]&(1<<31));
	const uint32 Q20bu = Q[offset+20];
	const uint32 Q21mask = (1<<31)|(1<<29);//|(1<<27);
	const uint32 Q21mask2 = (1<<31)|(1<<29)|(1<<27);
	const uint32 Q21val = ((0-(Q[offset+20]>>31))&((1<<31)|(1<<29))) | ((Q[offset+19]>>2)&(1<<27));
	const uint32 Q21bu = Q[offset+21];
		const uint32 m16bu = m[16], m17bu = m[17], Q17bu = Q[offset+17];
	if ((Q20bu&Q20mask)==Q20val && ((Q21bu^Q21val)&Q21mask2)==0) {
		step_21();
	}
#define m15tunnel(m15add) \
	if (((Q20bu+(m15add<<20))&Q20mask)==Q20val && (((Q21bu+(m15add<<25))^Q21val)&Q21mask)==0) {\
		m[15] += m15add; Q[offset+16] += m15add; Q[offset+17] = Q17bu + (m15add<<5);\
		Qr30[offset+14] = rotate_left(Q[offset+14],30);\
		m[16] = m16bu; m[17] = m17bu;\
		compute_mt<18,20>();\
		compute_qt<17,20>();\
		if ((Q[offset+20]&Q20mask)==Q20val && (Q[offset+19]&((1<<31)|(1<<27)))==gQ19val \
			&& ((Q[offset+18]&2952790016)==2147483648) && ( (Q[offset+17]&((1<<31)|(1<<28)|(1<<1)))==((1<<28)^(1<<1)) ) \
			) {\
			compute_mt<20,21>();\
			compute_qt<20,21>();\
			if ((Q[offset+21]&Q21mask2)==Q21val)\
				step_21();\
		}\
		m[15] -= m15add; Q[offset+16] -= m15add;\
	}

	m15tunnel(1<<5);
	m15tunnel(2<<5);
	m15tunnel(3<<5);
	m15tunnel(4<<5);
	m15tunnel(5<<5);
	m15tunnel(6<<5);
	m15tunnel(7<<5);
	m15tunnel(8<<5);
	m15tunnel(9<<5);
	m15tunnel(10<<5);
	m15tunnel(11<<5);
	m15tunnel(12<<5);
	m15tunnel(13<<5);
	m15tunnel(14<<5);
	m15tunnel(15<<5);
}

void step_18b()
{
	UPDATE(18);
	const uint32 Q19mask = (1<<31)|(1<<27);
	gQ19val = (1<<31)^(rotate_left(Q[offset+17],30)&(1<<27));
	const uint32 Q19bu = Q[offset+19];
	const uint32 m16 = m[16];
	if ((Q19bu&(1<<31))==(1<<31)) {
		const uint32 m17 = m[17];
		if (((Q19bu&Q19mask)==gQ19val) && ((Q[offset+18]&2952790016)==2147483648) && ( (Q[offset+17]&((1<<31)|(1<<28)|(1<<1)))==((1<<28)^(1<<1)) ))
			step_19();
#define M15tunnel(m15add,m14add) \
			if (((Q19bu+(m15add<<15)+(m14add<<20))&Q19mask)==gQ19val) {\
				m[15] += m15add; Q[offset+16] += m15add; Q[offset+17] = Q17pc + rotate_left(Q[offset+16],5);\
				m[16] = m16; m[17] = m17; \
				compute_mt<18,19>();\
				Qr30[offset+14] = rotate_left(Q[offset+14],30);\
				compute_qt<17,19>();\
				if (((Q[offset+19]&Q19mask)==gQ19val) && ((Q[offset+18]&2952790016)==2147483648) && ( (Q[offset+17]&((1<<31)|(1<<28)|(1<<1)))==((1<<28)^(1<<1)) ))\
					step_19();\
				m[15] -= m15add; Q[offset+16] -= m15add;\
			}

		Qr30[offset+14] = rotate_left(Q[offset+14],30);
		const uint32 Q17pc = sha1_ac[0] + sha1_f1(Q[offset+15],Qr30[offset+14],Qr30[offset+13]) + Qr30[offset+12] + m16;
		M15tunnel( (1<<9), 0 ); // 9
		M15tunnel( (2<<9), 0 ); // 10
		M15tunnel( (3<<9), 0 ); // 9,10
		M15tunnel( (8<<9), 0 ); // 12
		M15tunnel( (9<<9), 0 ); // 9,12
		M15tunnel( (10<<9), 0 ); // 10,12
		M15tunnel( (11<<9), 0 ); // 9,10,12
	}

#define M14tunnel(m14add) \
	if (((Q19bu+(m14add<<20))&(1<<31))==(1<<31)) {\
		m[14] += m14add; Q[offset+15] += m14add; Q[offset+16] += m14add<<5;\
		compute_mt<17,18>();\
		const uint32 m17 = m[17];\
		Qr30[offset+14] = rotate_left(Q[offset+14],30);\
		const uint32 Q17pc = sha1_ac[0] + sha1_f1(Q[offset+15],Qr30[offset+14],Qr30[offset+13]) + Qr30[offset+12] + m16;\
		M15tunnel( (0<<9), m14add ); \
		M15tunnel( (1<<9), m14add ); \
		M15tunnel( (2<<9), m14add ); \
		M15tunnel( (3<<9), m14add ); \
		M15tunnel( (8<<9), m14add ); \
		M15tunnel( (9<<9), m14add ); \
		M15tunnel( (10<<9), m14add ); \
		M15tunnel( (11<<9), m14add ); \
		m[14] -= m14add; Q[offset+15] -= m14add; Q[offset+16] -= m14add<<5;\
	}
	M14tunnel( (1<<7) );
	M14tunnel( (2<<7) );
	M14tunnel( (3<<7) );
	M14tunnel( (4<<7) );
	M14tunnel( (5<<7) );
	M14tunnel( (6<<7) );
	M14tunnel( (7<<7) );
}
void step_18()
{
	UPDATE(17);
	compute_mt<18,19>();
	compute_qt<18,19>();
	step_18b();
	if (Q[offset+1]&(1<<7)) {
		Q[offset+1]-=1<<7; m[0] -= 1<<7; m[1] += 1<<12; m[5] += 1<<5;
		Q[offset+13]+=1<<10; Qr30[offset+13] = rotate_left(Q[offset+13],30);
		m[12]+=1<<10; m[13]-=1<<15;
		compute_mt<16,19>();
		compute_qt<16,19>();
		step_18b();
		Q[offset+13]-=1<<10; Qr30[offset+13] = rotate_left(Q[offset+13],30);
		m[12]-=1<<10; m[13]+=1<<15;
		Q[offset+1]+=1<<7; m[0] += 1<<7; m[1] -= 1<<12; m[5] -= 1<<5;
	} else {
		Q[offset+1]+=1<<7; m[0] += 1<<7; m[1] -= 1<<12; m[5] -= 1<<5;
		Q[offset+13]+=1<<10; Qr30[offset+13] = rotate_left(Q[offset+13],30);
		m[12]+=1<<10; m[13]-=1<<15;
		compute_mt<16,19>();
		compute_qt<16,19>();
		step_18b();
		Q[offset+13]-=1<<10; Qr30[offset+13] = rotate_left(Q[offset+13],30);
		m[12]-=1<<10; m[13]+=1<<15;
		Q[offset+1]-=1<<7; m[0] -= 1<<7;
		m[1] += 1<<12; m[5] += 1<<5;
	}
}

void step_17()
{
	UPDATE(16);
	compute_mt<17,18>();
	compute_qt<17,18>();
	const uint32 Q18bu = Q[offset+18];
	if ((Q18bu&2952790016)==2147483648) {
		step_18();
	}
	if (((Q18bu+(1<<25))&2952790016)==2147483648) {
		m[14] += 1<<10; Q[offset+15] += 1<<10; Q[offset+16] += 1<<15;
		compute_mt<16,18>();
		compute_qt<16,18>();
		if ( ((Q[offset+18]&2952790016)==2147483648) & ( (Q[offset+17]&((1<<31)|(1<<28)|(1<<1)))==((1<<28)^(1<<1)) ) )
			step_18();
		m[14] -= 1<<10; Q[offset+15] -= 1<<10; Q[offset+16] -= 1<<15;
	}
	const uint32 Q18budiff = Q18bu + ((1<<27) - ((m[14]<<16)&(1<<28))); // m14[!12!] = 1 => Q18diff = -(1<<27) // m14[!12!] = 0 => Q18diff = +(1<<27)
	if (((Q18budiff)&2952790016)==2147483648) {
		Q[offset+1]+=1<<7; m[0] += 1<<7; m[1] -= 1<<12; m[5] -= 1<<5;
		if (m[14]&(1<<12)) {
			m[14] -= 1<<12; Q[offset+15] -= 1<<12; Q[offset+16] -= 1<<17;
			compute_mt<16,18>();
			compute_qt<16,18>();
			if ( ((Q[offset+18]&2952790016)==2147483648) & ( (Q[offset+17]&((1<<31)|(1<<28)|(1<<1)))==((1<<28)^(1<<1)) ) )
				step_18();
			m[14] += 1<<12; Q[offset+15] += 1<<12; Q[offset+16] += 1<<17;
		} else {
			m[14] += 1<<12;	Q[offset+15] += 1<<12; Q[offset+16] += 1<<17;
			compute_mt<16,18>();
			compute_qt<16,18>();
			if ( ((Q[offset+18]&2952790016)==2147483648) & ( (Q[offset+17]&((1<<31)|(1<<28)|(1<<1)))==((1<<28)^(1<<1)) ) )
				step_18();
			m[14] -= 1<<12; Q[offset+15] -= 1<<12; Q[offset+16] -= 1<<17;
		}
		Q[offset+1]-=1<<7; m[0] -= 1<<7; m[1] += 1<<12; m[5] += 1<<5;
	}
	if (((Q18budiff+(1<<25))&2952790016)==2147483648) {
		Q[offset+1]+=1<<7; m[0] += 1<<7; m[1] -= 1<<12; m[5] -= 1<<5;
		if (m[14]&(1<<12)) {
			m[14] += 0 - (1<<12) + (1<<10); Q[offset+15] += 0 - (1<<12) + (1<<10); Q[offset+16] += 0 - (1<<17) + (1<<15);
			compute_mt<16,18>();
			compute_qt<16,18>();
			if ( ((Q[offset+18]&2952790016)==2147483648) & ( (Q[offset+17]&((1<<31)|(1<<28)|(1<<1)))==((1<<28)^(1<<1)) ) )
				step_18();
			m[14] -= 0 - (1<<12) + (1<<10); Q[offset+15] -= 0 - (1<<12) + (1<<10); Q[offset+16] -= 0 - (1<<17) + (1<<15);
		} else {
			m[14] += (1<<12) + (1<<10); Q[offset+15] += (1<<12) + (1<<10); Q[offset+16] += (1<<17) + (1<<15);
			compute_mt<16,18>();
			compute_qt<16,18>();
			if ( ((Q[offset+18]&2952790016)==2147483648) & ( (Q[offset+17]&((1<<31)|(1<<28)|(1<<1)))==((1<<28)^(1<<1)) ) )
				step_18();
			m[14] -= (1<<12) + (1<<10); Q[offset+15] -= (1<<12) + (1<<10); Q[offset+16] -= (1<<17) + (1<<15);
		}
		Q[offset+1]-=1<<7; m[0] -= 1<<7; m[1] += 1<<12; m[5] += 1<<5;
	}
}

void step_15()
{
	const unsigned t = 15;
	UPDATE(t);
	Qr30[offset+t-2] = rotate_left(Q[offset+t-2],30);
	
	uint32 m13bu = m[13], Q14bu = Q[offset+14], m14bu = m[14], Q15bu = Q[offset+15], m13adj = 0;
	uint32 m13ok = 0, cnt = 0;
	const uint32 m13mask = 9952;
	do {
		++cnt;
		m[13] = m13bu ^ m13adj;
		m13adj -= 1; m13adj &= m13mask;
		Q[offset+14] = Q14bu + (m[13]-m13bu);
		m[13] ^= ((Q[offset+14]^Q14bu) & 256);
		Q[offset+14] = Q14bu + (m[13]-m13bu);
		const uint32 m14xor = (rotate_left(m[13]^m13bu,2)&2048); //2048=[!11!], 512=[!9!];
		const uint32 Q15adj = rotate_left(Q[offset+14],5) - rotate_left(Q14bu,5);
	
	const uint32 mpartial2 = 0 - (sha1_f1(Q[offset+t-1], Qr30[offset+t-2], Qr30[offset+t-3]) + sha1_ac[0] + Qr30[offset+t-4]);
		m[14] = m14bu ^ m14xor;
		Q[offset+t] = Q15bu + Q15adj + (m[14]-m14bu);
		const uint32 metset1 = metset1precomp[14][15];
		const uint32 Qtp1val = Qvalue[offset+t+1];
		const uint32 mpartial = mpartial2 - rotate_left(Q[offset+t],5);
		Q[offset+t+1] = metset1-mpartial;
		if (0 != ((Q[offset+t+1]^Qtp1val)&3892314114)) {
			if (cnt >= 2 && m13ok == 0) break;
			continue;
		}
		if ((Q[offset+14]^Q14bu) & 805306386) continue;
		if ((Q[offset+t]^Q15bu) & 2818572355) continue;

		m[t] = metset1;
		time_avg[t] += 1;//required to disable auto restart to step7
		++m13ok;

		compute_mt<16,17>();
		compute_qt<16,17>();
		if ((Q[offset+17]&2415919104)!=268435456) continue;
		
		if ((Q[offset+17]&2)!=2) {
			Q[offset+7] ^= 1<<5; Q[offset+12] ^= 1<<3; Qr30[offset+12] = rotate_left(Q[offset+12],30);
			m[6] += 1<<5; m[7] -= 1<<10; m[12] -= 1<<8;
			Q[offset+17] += 1<<2;
			step_17();
			Q[offset+7] ^= 1<<5; Q[offset+12] ^= 1<<3; Qr30[offset+12] = rotate_left(Q[offset+12],30);
			m[6] -= 1<<5; m[7] += 1<<10; m[12] += 1<<8;
		} else
			step_17();
	} while (m13adj != 0);
	m[13] = m13bu;
	Q[offset+14] = Q14bu;
}
void step_14()
{
	const unsigned t = 14;
	if (time_avg[40]) ++time_avg[t];
	UPDATE(t);
	Qr30[offset+t-2] = rotate_left(Q[offset+t-2],30);
	m[t-1] = *Qtp1valsvec[t-1] + metpartialvec[t-1];
	const uint32 metset13m13precomp = metset1precomp[13][14] ^ 0
				^((0-(m[13]&(1<<0)))&5748736) //5748736=[!11,12,13,15,16,17,18,20,22!]
				^(rotate_left(m[13],2)&2048) //2048=[!11!], 512=[!9!]
				^(rotate_left(m[13],14)&4096) //4096=[!12!], 1073741824=[!30!]
				;	
	const uint32 m12mask = 159744;
	uint32 m12bu = m[12], Q13bu = Q[offset+13], m12adj = 0;
	uint32 m12okcnt = 0;
	do {
		m[12] = m12bu ^ m12adj;
		m12adj -= 1; m12adj &= m12mask;
		Q[offset+13] = Q13bu + (m[12]-m12bu);
		if ((Q[offset+13]^Q13bu)&2550137872) continue;
		const uint32 Q14adj = rotate_left(Q[offset+13],5)-rotate_left(Q13bu,5);

		const uint32 m14precomp = metset13m13precomp
				^(rotate_left(m[12]^m12bu,31)&31455235) //31455235=[!0,1,11,12,13,14,15,16,17,18,19,20,22,23,24!], 62910470=[!1,2,12,13,14,15,16,17,18,19,20,21,23,24,25!]
				^(rotate_left(m[12]^m12bu,29)&8153088) //8153088=[!11,13,14,18,19,20,21,22!], 65224704=[!14,16,17,21,22,23,24,25!]
				^(rotate_left(m[12]^m12bu,30)&2099200) //2099200=[!11,21!], 8396800=[!13,23!]
				;
		const uint32 m15precomp = 0
				^(rotate_left(m[12]^m12bu,28)&1076600832) //1076600832=[!13,15,16,17,19,21,30!], 45744132=[!2,17,19,20,21,23,25!]
				;		
	const uint32 mpartial2 = 0 - sha1_f1(Q[offset+t-1], Qr30[offset+t-2], Qr30[offset+t-3]) - sha1_ac[0] - Qr30[offset+t-4];
	for (uint32* Qtvalsptr = Qtp1valsvec[t-1]; Qtvalsptr < Qtp1valsvecptr[t-1]; ++Qtvalsptr) {
		m[t-1] = *Qtvalsptr + metpartialvec[t-1];
		const uint32 metset1 = m14precomp // metset13m13precomp
//				metset1precomp[13][14] ^ 0
//				^((0-(m[13]&(1<<0)))&5748736) //5748736=[!11,12,13,15,16,17,18,20,22!]
				^((0-((m[13]>>14)&1))&5697536) //5697536=[!12,13,14,15,17,18,20,22!]
				^((0-((m[13]>>16)&1))&7389184) //7389184=[!14,15,20,21,22!]
				^((0-(m[13]&(1<<11)))&2297856) //2297856=[!12,16,17,21!]
				^((0-(m[13]&(1<<12)))&2297856) //2297856=[!12,16,17,21!]
//				^(rotate_left(m[13],2)&2048) //2048=[!11!], 512=[!9!]
//				^(rotate_left(m[13],14)&4096) //4096=[!12!], 1073741824=[!30!]
				;
		m[14] = metset1;
		Q[offset+t] = *Qtvalsptr + Q14adj;
		const uint32 mpartial = mpartial2 - rotate_left(Q[offset+t],5);
		Q[offset+t+1] = metset1 - mpartial;
		const uint32 Qtp1val = Qvalue[offset+t+1] ^ (Qprev[offset+t+1]&Q[offset+t]);
		if (Qtvalsptr == Qtp1valsvec[t-1] && 0 != ((Q[offset+t+1]^Qtp1val)&67)) {
			m[12] = m12bu;
			Q[offset+13] = Q13bu;
			return;
		}
		if (0 != ((Q[offset+t+1]^Qtp1val)&2818572355)) continue;
		if ((Q[offset+t]^*Qtvalsptr) & 805306386) continue;
		metset1precomp[14][15] = metset1precomp[13][15] ^ 0
				^((0-(m[13]&(1<<16)))&1100808192) //1100808192=[!16,18,19,20,23,24,30!]
				^((0-((m[13]>>14)&1))&9199620) //9199620=[!2,13,14,18,19,23!]
				^((0-(m[13]&(1<<0)))&1082679296) //1082679296=[!13,14,19,23,30!]
				^((0-(m[13]&(1<<11)))&16850944) //16850944=[!13,16,24!]
				^((0-(m[13]&(1<<12)))&16850944) //16850944=[!13,16,24!]
				^m15precomp;
				;
		step_15();
	}
	} while (m12adj != 0);
	m[12] = m12bu;
	Q[offset+13] = Q13bu;
}




#define M13BIT11 ((1<<11)|(1<<17)|(1<<19)|(1<<24))
#define M13BIT12 ((1<<12)|(1<<17)|(1<<19)|(1<<24))
#define M13BIT14 ((1<<14)|(1<<18)|(1<<19)|(1<<20)|(1<<21)|(1<<24))
#define M13BIT16 ((1<<16)|(1<<17)|(1<<18)|(1<<20))
const uint32 metcur13vals[1<<4] = {
	0, M13BIT11, M13BIT12, M13BIT11^M13BIT12,
	0^M13BIT14, M13BIT11^M13BIT14, M13BIT12^M13BIT14, M13BIT11^M13BIT12^M13BIT14,
	0^M13BIT16, M13BIT11^M13BIT16, M13BIT12^M13BIT16, M13BIT11^M13BIT12^M13BIT16,
	0^M13BIT16^M13BIT14, M13BIT11^M13BIT16^M13BIT14, M13BIT12^M13BIT16^M13BIT14, M13BIT11^M13BIT12^M13BIT16^M13BIT14
	};
	
bool step_13()
{
	const unsigned t = 13;
	if (time_avg[40]) ++time_avg[t];
	UPDATE(t);
	bool step13ok = false;
	Qr30[offset+t-2] = rotate_left(Q[offset+t-2],30);
	const uint32 mpartial2 = 0 - sha1_f1(Q[offset+t-1], Qr30[offset+t-2], Qr30[offset+t-3]) - sha1_ac[0] - Qr30[offset+t-4];
	const uint32 metmask = 3221127198;
	const uint32 m12bu = m[12] = *Qtp1valsvec[t-1] + metpartialvec[t-1];
	const uint32 metset1precomp12 = metset1precomp[12][13] ^ 0
				^((0-(m[12]&(1<<0)))&20709376) //20709376=[!18,19,20,21,24!]
				^((0-(m[12]&(1<<2)))&2165702656) //2165702656=[!17,18,20,24,31!]
				^((0-((m[12]>>30)&1))&19791872) //19791872=[!17,18,19,21,24!]
				^((0-(m[12]&(1<<18)))&3407872) //3407872=[!18,20,21!]
				^((0-((m[12]>>20)&1))&18350080) //18350080=[!19,20,24!]
				^((0-((m[12]>>22)&1))&2228224) //2228224=[!17,21!]
				^(rotate_left(m[12],30)&1966080) //1966080=[!17,18,19,20!], 7864320=[!19,20,21,22!]
				^(rotate_left(m[12],1)&16908288) //16908288=[!17,24!], 8454144=[!16,23!]
				^(rotate_left(m[12],28)&3145728) //3145728=[!20,21!], 50331648=[!24,25!]
				^(rotate_left(m[12],2)&131072) //131072=[!17!], 32768=[!15!]
				^(rotate_left(m[12],3)&16777216) //16777216=[!24!], 2097152=[!21!]
				^(rotate_left(m[12],23)&16777216) //16777216=[!24!], 2=[!1!]
				^(rotate_left(m[12],24)&131072) //131072=[!17!], 33554432=[!25!]
				^(rotate_left(m[12],26)&131072) //131072=[!17!], 8388608=[!23!]
				^(rotate_left(m[12],29)&2097152) //2097152=[!21!], 16777216=[!24!]
				;

	for (uint32* Qtvalsptr = Qtp1valsvecptr[t-1]-1; Qtvalsptr >= Qtp1valsvec[t-1]; --Qtvalsptr) {
		Q[offset+t] = *Qtvalsptr;
		m[t-1] = *Qtvalsptr + metpartialvec[t-1];
		bool didmp = false;
		const uint32 metset1 = metset1precomp12
				^((0-((m[12]^m12bu)&(1<<18)))&3407872) //3407872=[!18,20,21!]
				^(rotate_left(m[12]^m12bu,1)&16908288) //16908288=[!17,24!], 8454144=[!16,23!]
				^(rotate_left(m[12]^m12bu,2)&131072) //131072=[!17!], 32768=[!15!]
				;
		const uint32 Qtp1val = Qvalue[offset+t+1];// ^ (Qprev[offset+t+1]&Q[offset+t]);
		const uint32 metset1adj = metset1 ^ ((~Qtp1val) & 256);// ^ (xrng64()&1073839841);
		const uint32 mpartial = mpartial2 - rotate_left(Q[offset+t],5);
		metpartialvec[t] = mpartial;
		uint32* Qtp1valsptr = Qtp1valsvec[t];
		uint32 cur = 0; const uint32 curmask = 1|(1<<30);
		do { cur -= 1; cur &= curmask;
		const uint32 curadj = metset1adj ^ cur 
			^ (   (0-(cur&1))&( (1<<18)|(1<<19)|(1<<20)|(1<<21)|(1<<24) )   )
			;
		Qtp1valsptr = Qtp1valsvec[t];			
		for (unsigned jj = 0; jj < (1<<4); ++jj) {
//			m[t] = metcur13vals[jj] ^ curadj;
			Q[offset+t+1] = (metcur13vals[jj] ^ curadj) - mpartial;
			if (0 != ((Q[offset+t+1]^Qtp1val)&805306386)) break; //continue;
			uint32 Qtp1xorfix = (Q[offset+t+1]^Qtp1val) & 256;
			*(Qtp1valsptr++) = Q[offset+t+1]^Qtp1xorfix;
		}
		if (Qtp1valsptr == Qtp1valsvec[t]) continue;
		step13ok = true;
		if (!didmp) { UPDATE(73); 
		metset1precomp[13][14] = metset1precomp[12][14] ^ 0
				^((0-(m[12]&(1<<2)))&1086244864) //1086244864=[!11,14,15,17,18,19,20,21,23,30!]
				^((0-((m[12]>>18)&1))&7628800) //7628800=[!11,13,14,18,20,21,22!]
				^((0-((m[12]>>22)&1))&5566464) //5566464=[!12,13,14,15,18,20,22!]
				^((0-(m[12]&(1<<1)))&874496) //874496=[!11,12,14,16,18,19!]
				^((0-((m[12]>>20)&1))&5345280) //5345280=[!12,15,16,20,22!]
				^((0-((m[12]>>21)&1))&2330624) //2330624=[!12,15,16,17,21!]
				^((0-(m[12]&(1<<0)))&1474560) //1474560=[!15,17,18,20!]
				^((0-((m[12]>>30)&1))&3221504000) //3221504000=[!14,18,30,31!]
				^((0-((m[12]>>16)&1))&71680) //71680=[!11,12,16!]
				^((0-((m[12]>>15)&1))&67584) //67584=[!11,16!]
				^((0-((m[12]>>24)&1))&73728) //73728=[!13,16!]
				^(rotate_left(m[12],31)&31455235) //31455235=[!0,1,11,12,13,14,15,16,17,18,19,20,22,23,24!], 62910470=[!1,2,12,13,14,15,16,17,18,19,20,21,23,24,25!]
				^(rotate_left(m[12],29)&8153088) //8153088=[!11,13,14,18,19,20,21,22!], 65224704=[!14,16,17,21,22,23,24,25!]
				^(rotate_left(m[12],22)&5300224) //5300224=[!13,14,15,20,22!], 1132462081=[!0,23,24,25,30!]
				^(rotate_left(m[12],26)&532480) //532480=[!13,19!], 34078720=[!19,25!]
				^(rotate_left(m[12],30)&2099200) //2099200=[!11,21!], 8396800=[!13,23!]
				^(rotate_left(m[12],19)&4096) //4096=[!12!], 33554432=[!25!]
				^(rotate_left(m[12],25)&65536) //65536=[!16!], 8388608=[!23!]
				;
		metset1precomp[13][15] = metset1precomp[12][15] ^ 0
				^((0-(m[12]&(1<<1)))&24682500) //24682500=[!2,13,15,19,20,21,22,24!]
				^((0-((m[12]>>18)&1))&28114948) //28114948=[!2,16,18,19,21,23,24!]
				^((0-((m[12]>>22)&1))&25919492) //25919492=[!2,15,16,17,19,23,24!]
				^((0-((m[12]>>30)&1))&9871364) //9871364=[!2,13,15,17,18,20,23!]
				^((0-((m[12]>>20)&1))&1083998208) //1083998208=[!15,18,19,20,23,30!]
				^((0-((m[12]>>24)&1))&1074479108) //1074479108=[!2,14,16,17,19,30!]
				^((0-(m[12]&(1<<0)))&8929284) //8929284=[!2,14,19,23!]
				^((0-(m[12]&(1<<2)))&15728640) //15728640=[!20,21,22,23!]
				^((0-((m[12]>>23)&1))&17080320) //17080320=[!13,15,18,24!]
				^((0-((m[12]>>19)&1))&2121728) //2121728=[!13,14,21!]
				^((0-((m[12]>>25)&1))&1441792) //1441792=[!17,18,20!]
				^((0-((m[12]>>15)&1))&2105344) //2105344=[!13,21!]
				^((0-((m[12]>>16)&1))&2105344) //2105344=[!13,21!]
				^((0-((m[12]>>21)&1))&16793600) //16793600=[!14,24!]
				^(rotate_left(m[12],28)&1076600832) //1076600832=[!13,15,16,17,19,21,30!], 45744132=[!2,17,19,20,21,23,25!]
				;
		}
		didmp = true;
		Qtp1valsvecptr[t] = Qtp1valsptr;
		step_14();
		} while (cur != 0);
	}
	return true; // step13ok;
}
bool step_12()
{
	static bool firsttime = true; if (firsttime) { cout << "t12 " << endl; firsttime = false; }
	const unsigned t = 12;
	if (time_avg[40]) ++time_avg[t];
	UPDATE(t);
	show_performance_data(t);
	bool step12ok = false;
	Qr30[offset+t-2] = rotate_left(Q[offset+t-2],30);
	const uint32 mpartial2 = 0 - sha1_f1(Q[offset+t-1], Qr30[offset+t-2], Qr30[offset+t-3]) - sha1_ac[0] - Qr30[offset+t-4];
	const uint32 metmask = 3154119704;
	for (uint32* Qtvalsptr = Qtp1valsvecptr[t-1]-1; Qtvalsptr >= Qtp1valsvec[t-1]; --Qtvalsptr) {
		Q[offset+t] = *Qtvalsptr;
		m[t-1] = *Qtvalsptr + metpartialvec[t-1];
		bool didmp = false;
		bool s13ok = false;
		const uint32 metset1 = metset1precomp[11][12];
		const uint32 Qtp1val = Qvalue[offset+t+1] ^ (Qprev[offset+t+1]&Q[offset+t]);
		const uint32 metset1adj = metset1 ^ ((~Qtp1val) & 258);
		const uint32 mpartial = mpartial2 - rotate_left(Q[offset+t],5);
		metpartialvec[t] = mpartial;
		uint32* Qtp1valsptr = Qtp1valsvec[t];
		uint32 cur = 0; const uint32 curmask = 1140327141;//1136657125;
		do { cur -= 1; cur &= curmask;
		uint32 metcur = 0;
		Qtp1valsptr = Qtp1valsvec[t];
		do {
			m[t] = metcur ^ cur ^ metset1adj;
			metcur -= 1; metcur &= 1140847333^curmask^159744; // 21 bits of freedom
			Q[offset+t+1] = m[t] - mpartial;
			// don't check for Q13[31]
			if (0 != ((Q[offset+t+1]^Qtp1val) & (2550137872^(1<<31)) )) break;
			uint32 Qtp1xorfix = (Q[offset+t+1]^Qtp1val) & 258;
			// compute fixed m[t]
			m[t] = (Q[offset+t+1]^Qtp1xorfix) + mpartial;
			if ((m[t]&768)==0) continue; // tunnel Q7-5 Q12-3 me condition
			m[t] ^= (m[t]&(1<<1))<<30; // intrel bit 31: (12,1)(12,31)
			Q[offset+t+1] = m[t] - mpartial;
			// check for Q13[31] (and the rest)
			if (0 != ((Q[offset+t+1]^Qtp1val) & (2550137872) )) continue;
			*(Qtp1valsptr++) = Q[offset+t+1];
		} while (metcur != 0);
		if (Qtp1valsptr == Qtp1valsvec[t]) continue;
		step12ok = true;
		if (!didmp) {
		metset1precomp[12][13] = metset1precomp[11][13] ^ 0
				^((0-(m[11]&(1<<0)))&4063232) //4063232=[!17,18,19,20,21!]
				^((0-(m[11]&(1<<15)))&3538944) //3538944=[!17,18,20,21!]
				^((0-((m[11]>>31)&1))&3538944) //3538944=[!17,18,20,21!]
				^((0-(m[11]&(1<<12)))&17432576) //17432576=[!17,19,24!]
				^((0-(m[11]&(1<<13)))&17432576) //17432576=[!17,19,24!]
				^((0-((m[11]>>20)&1))&3407872) //3407872=[!18,20,21!]
				^((0-((m[11]>>21)&1))&17432576) //17432576=[!17,19,24!]
				^(rotate_left(m[11],31)&2178416640) //2178416640=[!19,20,22,23,24,31!], 61865985=[!0,20,21,23,24,25!]
				^(rotate_left(m[11],29)&6029312) //6029312=[!18,19,20,22!], 48234496=[!21,22,23,25!]
				^(rotate_left(m[11],26)&917504) //917504=[!17,18,19!], 58720256=[!23,24,25!]
				^(rotate_left(m[11],1)&1048576) //1048576=[!20!], 524288=[!19!]
				^(rotate_left(m[11],3)&131072) //131072=[!17!], 16384=[!14!]
				^(rotate_left(m[11],4)&2097152) //2097152=[!21!], 131072=[!17!]
				^(rotate_left(m[11],25)&131072) //131072=[!17!], 16777216=[!24!]
				;
		metset1precomp[12][14] = metset1precomp[11][14] ^ 0
				^((0-(m[11]&(1<<0)))&3227236352) //3227236352=[!11,12,13,15,16,17,19,20,22,30,31!]
				^((0-((m[11]>>20)&1))&7665664) //7665664=[!11,12,13,14,15,18,20,21,22!]
				^((0-((m[11]>>15)&1))&7725056) //7725056=[!13,14,15,16,18,20,21,22!]
				^((0-((m[11]>>24)&1))&1439744) //1439744=[!11,12,13,14,15,16,18,20!]
				^((0-((m[11]>>31)&1))&7710720) //7710720=[!11,13,15,16,18,20,21,22!]
				^((0-((m[11]>>19)&1))&7428096) //7428096=[!11,12,14,16,20,21,22!]
				^((0-((m[11]>>23)&1))&587776) //587776=[!11,12,13,14,15,19!]
				^((0-((m[11]>>12)&1))&2299904) //2299904=[!11,12,16,17,21!]
				^((0-((m[11]>>21)&1))&2177024) //2177024=[!11,12,13,16,21!]
				^((0-((m[11]>>13)&1))&2297856) //2297856=[!12,16,17,21!]
				^((0-((m[11]>>30)&1))&2147561472) //2147561472=[!12,13,16,31!]
				^((0-(m[11]&(1<<1)))&77824) //77824=[!12,13,16!]
				^((0-((m[11]>>14)&1))&71680) //71680=[!11,12,16!]
				^((0-((m[11]>>17)&1))&329728) //329728=[!11,16,18!]
				^((0-((m[11]>>18)&1))&83968) //83968=[!11,14,16!]
				^((0-((m[11]>>22)&1))&86016) //86016=[!12,14,16!]
				^((0-((m[11]>>25)&1))&2260992) //2260992=[!15,17,21!]
				^(rotate_left(m[11],1)&2048) //2048=[!11!], 1024=[!10!]
				;
		metset1precomp[12][15] = metset1precomp[11][15] ^ 0
				^((0-(m[11]&(1<<0)))&1104470016) //1104470016=[!13,14,15,18,20,22,23,24,30!]
				^((0-((m[11]>>20)&1))&26173444) //26173444=[!2,13,14,16,17,18,19,23,24!]
				^((0-((m[11]>>19)&1))&1102848000) //1102848000=[!13,18,19,20,21,23,24,30!]
				^((0-((m[11]>>15)&1))&26034180) //26034180=[!2,14,16,18,19,23,24!]
				^((0-((m[11]>>24)&1))&1075011588) //1075011588=[!2,13,14,16,17,20,30!]
				^((0-((m[11]>>31)&1))&27869188) //27869188=[!2,14,16,19,21,23,24!]
				^((0-(m[11]&(1<<12)))&16850944) //16850944=[!13,16,24!]
				^((0-((m[11]>>22)&1))&1074790404) //1074790404=[!2,20,30!]
				^((0-((m[11]>>25)&1))&2236416) //2236416=[!13,17,21!]
				^((0-(m[11]&(1<<13)))&16785408) //16785408=[!13,24!]
				^((0-((m[11]>>14)&1))&2105344) //2105344=[!13,21!]
				^((0-((m[11]>>17)&1))&1073741828) //1073741828=[!2,30!]
				^(rotate_left(m[11],29)&1079812096) //1079812096=[!13,15,18,19,20,22,30!], 48562178=[!1,16,18,21,22,23,25!]
				^(rotate_left(m[11],3)&19988480) //19988480=[!16,20,21,24!], 2498560=[!13,17,18,21!]
				^(rotate_left(m[11],25)&376832) //376832=[!14,15,16,18!], 48234496=[!21,22,23,25!]
				^(rotate_left(m[11],27)&73728) //73728=[!13,16!], 2359296=[!18,21!]
				^(rotate_left(m[11],20)&2097152) //2097152=[!21!], 2=[!1!]
				^(rotate_left(m[11],23)&2097152) //2097152=[!21!], 1073741824=[!30!]
				^(rotate_left(m[11],24)&32768) //32768=[!15!], 8388608=[!23!]
				;
		}
		didmp = true;
		Qtp1valsvecptr[t] = Qtp1valsptr;
		if (step_13()) s13ok = true;
		} while (cur != 0);
		if (!s13ok) return step12ok;
	}
	return step12ok;
}
bool step_11()
{
	static bool firsttime = true; if (firsttime) { cout << "t11 " << flush; firsttime = false; }
	const unsigned t = 11;
	if (time_avg[40]) ++time_avg[t];
	UPDATE(t);
	show_performance_data(t);
	bool step11ok = false;
	Qr30[offset+t-2] = rotate_left(Q[offset+t-2],30);
	const uint32 mpartial2 = 0 - sha1_f1(Q[offset+t-1], Qr30[offset+t-2], Qr30[offset+t-3]) - sha1_ac[0] - Qr30[offset+t-4];
	const uint32 metmask = 1006633212;
	for (uint32* Qtvalsptr = Qtp1valsvecptr[t-1]-1; Qtvalsptr >= Qtp1valsvec[t-1]; --Qtvalsptr) {
		Q[offset+t] = *Qtvalsptr;
		m[t-1] = *Qtvalsptr + metpartialvec[t-1];
		const uint32 metset1 = metset1precomp[10][11] ^ 0
				;
		const uint32 Qtp1val = Qvalue[offset+t+1] ^ (Qprev[offset+t+1]&Q[offset+t]);
		const uint32 metset1adj = metset1 ^ ((~Qtp1val) & 3221229570) ^ (xrng64()&67104513);
		const uint32 mpartial = mpartial2 - rotate_left(Q[offset+t],5);
		metpartialvec[t] = mpartial;
		bool didmp = false;
		bool step12ok = false;
		//uint32* Qtp1valsptr = Qtp1valsvec[t];
		uint32 cur = 0; const uint32 curmask = 62914561; // 5 bits
		do { cur -= 1; cur &= curmask;
		uint32* Qtp1valsptr = Qtp1valsvec[t];
		uint32 metcur = 0;
		do {
			m[t] = metcur ^ cur ^ metset1adj;
			metcur -= 1; metcur &= 67104513^curmask; // 18 bits of freedom
			Q[offset+t+1] = m[t] - mpartial;
			if (0 != ((Q[offset+t+1]^Qtp1val)&134217848)) break;
			uint32 Qtp1xorfix = (Q[offset+t+1]^Qtp1val) & 3221229570;
			*(Qtp1valsptr++) = Q[offset+t+1]^Qtp1xorfix;
		} while (metcur != 0);
		//} while (cur != 0);
		if (Qtp1valsptr == Qtp1valsvec[t]) continue;
		step11ok = true;
		if (!didmp) {
			didmp = true;
			metset1precomp[11][12] = metset1precomp[10][12] ^ 0
					^(rotate_left(m[10],1)&2147483648) //2147483648=[!31!], 1073741824=[!30!]
					;
			metset1precomp[11][13] = metset1precomp[10][13] ^ 0
					^((0-((m[10]>>30)&1))&20840448) //20840448=[!17,18,19,20,21,24!]
					^((0-((m[10]>>22)&1))&20578304) //20578304=[!17,19,20,21,24!]
					^((0-((m[10]>>19)&1))&20185088) //20185088=[!18,20,21,24!]
					^((0-((m[10]>>25)&1))&3538944) //3538944=[!17,18,20,21!]
					^((0-(m[10]&(1<<15)))&17432576) //17432576=[!17,19,24!]
					^((0-((m[10]>>18)&1))&3276800) //3276800=[!17,20,21!]
					^((0-((m[10]>>20)&1))&17563648) //17563648=[!18,19,24!]
					^((0-((m[10]>>24)&1))&917504) //917504=[!17,18,19!]
					^((0-(m[10]&(1<<13)))&17301504) //17301504=[!19,24!]
					^((0-((m[10]>>21)&1))&17301504) //17301504=[!19,24!]
					^((0-((m[10]>>23)&1))&1572864) //1572864=[!19,20!]
					^((0-((m[10]>>31)&1))&17039360) //17039360=[!18,24!]
					^(rotate_left(m[10],0)&4063232) //4063232=[!17,18,19,20,21!], 4063232=[!17,18,19,20,21!]
					^(rotate_left(m[10],20)&3145728) //3145728=[!20,21!], 3=[!0,1!]
					^(rotate_left(m[10],17)&262144) //262144=[!18!], 2=[!1!]
					^(rotate_left(m[10],21)&2097152) //2097152=[!21!], 1=[!0!]
					;
			metset1precomp[11][14] = metset1precomp[10][14] ^ 0
					^((0-((m[10]>>25)&1))&5208064) //5208064=[!11,12,13,14,16,17,18,19,22!]
					^((0-((m[10]>>30)&1))&2153238528) //2153238528=[!12,14,15,16,17,18,20,22,31!]
					^((0-((m[10]>>31)&1))&3225202688) //3225202688=[!12,13,15,18,19,20,21,30,31!]
					^((0-((m[10]>>18)&1))&7632896) //7632896=[!11,12,13,14,18,20,21,22!]
					^((0-((m[10]>>19)&1))&5625856) //5625856=[!11,12,14,15,16,18,20,22!]
					^((0-(m[10]&(1<<1)))&3561472) //3561472=[!11,12,14,17,18,20,21!]
					^((0-((m[10]>>20)&1))&5355520) //5355520=[!11,12,13,15,16,20,22!]
					^((0-((m[10]>>22)&1))&5179392) //5179392=[!11,16,17,18,19,22!]
					^((0-((m[10]>>24)&1))&1468416) //1468416=[!11,13,14,17,18,20!]
					^((0-(m[10]&(1<<0)))&4528128) //4528128=[!11,12,16,18,22!]
					^((0-((m[10]>>21)&1))&2279424) //2279424=[!11,14,15,17,21!]
					^((0-((m[10]>>17)&1))&88064) //88064=[!11,12,14,16!]
					^((0-(m[10]&(1<<15)))&2293760) //2293760=[!16,17,21!]
					^((0-((m[10]>>23)&1))&4329472) //4329472=[!12,17,22!]
					^((0-(m[10]&(1<<13)))&2228224) //2228224=[!17,21!]
					^((0-((m[10]>>16)&1))&10240) //10240=[!11,13!]
					^(rotate_left(m[10],30)&3230464000) //3230464000=[!11,12,13,14,15,18,19,23,30,31!], 36954115=[!0,1,13,14,15,16,17,20,21,25!]
					;
			metset1precomp[11][15] = metset1precomp[10][15] ^ 0
					^((0-(m[10]&(1<<1)))&3247939584) //3247939584=[!13,15,16,17,18,20,23,24,30,31!]
					^((0-((m[10]>>21)&1))&1092214788) //1092214788=[!2,13,14,15,16,19,20,24,30!]
					^((0-((m[10]>>22)&1))&10313732) //10313732=[!2,13,14,16,18,19,20,23!]
					^((0-((m[10]>>23)&1))&1092558848) //1092558848=[!13,16,17,18,19,20,24,30!]
					^((0-((m[10]>>24)&1))&1090068480) //1090068480=[!13,16,19,20,21,22,23,30!]
					^((0-((m[10]>>31)&1))&14426112) //14426112=[!13,18,19,20,22,23!]
					^((0-(m[10]&(1<<0)))&2736128) //2736128=[!14,15,16,19,21!]
					^((0-((m[10]>>18)&1))&25706500) //25706500=[!2,14,19,23,24!]
					^((0-((m[10]>>19)&1))&8798212) //8798212=[!2,14,17,18,23!]
					^((0-((m[10]>>20)&1))&1082679296) //1082679296=[!13,14,19,23,30!]
					^((0-((m[10]>>30)&1))&9191424) //9191424=[!14,18,19,23!]
					^((0-(m[10]&(1<<13)))&18939904) //18939904=[!16,21,24!]
					^((0-(m[10]&(1<<15)))&16842752) //16842752=[!16,24!]
					^((0-((m[10]>>17)&1))&2105344) //2105344=[!13,21!]
					^((0-((m[10]>>25)&1))&532480) //532480=[!13,19!]
					^(rotate_left(m[10],0)&3261325315) //3261325315=[!0,1,13,14,15,16,17,21,22,25,30,31!], 3261325315=[!0,1,13,14,15,16,17,21,22,25,30,31!]
					^(rotate_left(m[10],30)&8437760) //8437760=[!14,15,23!], 33751040=[!16,17,25!]
					;
		}
		Qtp1valsvecptr[t] = Qtp1valsptr;
		if (step_12()) step12ok = true;
		} while (cur != 0);
		if (!step12ok) return step11ok;
	}
	return step11ok;
}
bool step_10()
{
	static bool firsttime = true; if (firsttime) { cout << "t10 " << flush; firsttime = false; }
	const unsigned t = 10;
	UPDATE(t);
	show_performance_data(t);
	bool step10ok = false;
	Qr30[offset+t-2] = rotate_left(Q[offset+t-2],30);
	const uint32 mpartial2 = 0 - sha1_f1(Q[offset+t-1], Qr30[offset+t-2], Qr30[offset+t-3]) - sha1_ac[0] - Qr30[offset+t-4];
	const uint32 metmask = 1006639132;
	for (uint32* Qtvalsptr = Qtp1valsvecptr[t-1]-1; Qtvalsptr >= Qtp1valsvec[t-1]; --Qtvalsptr) {
		Q[offset+t] = *Qtvalsptr;
		m[t-1] = *Qtvalsptr + metpartialvec[t-1];
		const uint32 metset1 = metset1precomp[9][10] ^ 0
				;
		const uint32 Qtp1val = Qvalue[offset+t+1] ^ (Qprev[offset+t+1]&Q[offset+t]);
		const uint32 metset1adj = metset1 ^ ((~Qtp1val) & 289) ^ (xrng64()&3288327874);
		const uint32 mpartial = mpartial2 - rotate_left(Q[offset+t],5);
		metpartialvec[t] = mpartial;
		bool didmp = false;
		bool step11ok = false;
		//uint32* Qtp1valsptr = Qtp1valsvec[t];
		uint32 cur = 0; const uint32 curmask = 66060290;// 62914562; // 5 bits
		do { cur -= 1; cur &= curmask;
		uint32* Qtp1valsptr = Qtp1valsvec[t];
		uint32 metcur = 0;
		do {
			m[t] = metcur ^ cur ^ metset1adj;
			metcur -= 1; metcur &= 3288327874^curmask; // 20 bits of freedom
			Q[offset+t+1] = m[t] - mpartial;
			if (0 != ((Q[offset+t+1]^Qtp1val)&671088656)) break;
			uint32 Qtp1xorfix = (Q[offset+t+1]^Qtp1val) & 289;
			*(Qtp1valsptr++) = Q[offset+t+1]^Qtp1xorfix;
		} while (metcur != 0);
		//} while (cur != 0);
		if (Qtp1valsptr == Qtp1valsvec[t]) continue;
		step10ok = true;
		if (!didmp) {
			didmp = true;
			metset1precomp[10][11] = metset1precomp[9][11] ^ 0
					;
			metset1precomp[10][12] = metset1precomp[9][12] ^ 0
					^(rotate_left(m[9],31)&2147483648) //2147483648=[!31!], 1=[!0!]
					;
			metset1precomp[10][13] = metset1precomp[9][13] ^ 0
					^((0-(m[9]&(1<<17)))&20840448) //20840448=[!17,18,19,20,21,24!]
					^((0-(m[9]&(1<<1)))&4063232) //4063232=[!17,18,19,20,21!]
					^((0-(m[9]&(1<<16)))&20709376) //20709376=[!18,19,20,21,24!]
					^((0-((m[9]>>31)&1))&3538944) //3538944=[!17,18,20,21!]
					^((0-(m[9]&(1<<13)))&17432576) //17432576=[!17,19,24!]
					^((0-(m[9]&(1<<0)))&1572864) //1572864=[!19,20!]
					^((0-(m[9]&(1<<14)))&17301504) //17301504=[!19,24!]
					^(rotate_left(m[9],30)&2179596288) //2179596288=[!17,19,21,22,23,24,31!], 128450562=[!1,19,21,23,24,25,26!]
					^(rotate_left(m[9],31)&18743296) //18743296=[!17,18,19,20,24!], 37486592=[!18,19,20,21,25!]
					^(rotate_left(m[9],0)&20185088) //20185088=[!18,20,21,24!], 20185088=[!18,20,21,24!]
					^(rotate_left(m[9],1)&20447232) //20447232=[!19,20,21,24!], 10223616=[!18,19,20,23!]
					^(rotate_left(m[9],27)&3014656) //3014656=[!17,18,19,21!], 96468992=[!22,23,24,26!]
					^(rotate_left(m[9],29)&14811136) //14811136=[!17,21,22,23!], 118489088=[!20,24,25,26!]
					^(rotate_left(m[9],2)&17956864) //17956864=[!17,20,24!], 4489216=[!15,18,22!]
					^(rotate_left(m[9],24)&393216) //393216=[!17,18!], 100663296=[!25,26!]
					^(rotate_left(m[9],25)&786432) //786432=[!18,19!], 100663296=[!25,26!]
					^(rotate_left(m[9],26)&393216) //393216=[!17,18!], 25165824=[!23,24!]
					^(rotate_left(m[9],28)&786432) //786432=[!18,19!], 12582912=[!22,23!]
					^(rotate_left(m[9],4)&16777216) //16777216=[!24!], 1048576=[!20!]
					^(rotate_left(m[9],6)&16777216) //16777216=[!24!], 262144=[!18!]
					;
			metset1precomp[10][14] = metset1precomp[9][14] ^ 0
					^((0-(m[9]&(1<<0)))&7163904) //7163904=[!12,14,16,18,19,21,22!]
					^((0-((m[9]>>31)&1))&7641088) //7641088=[!11,12,15,18,20,21,22!]
					^((0-(m[9]&(1<<1)))&5933056) //5933056=[!11,15,17,19,20,22!]
					^(rotate_left(m[9],0)&126742531) //126742531=[!0,1,12,13,14,15,16,18,19,23,24,25,26!], 126742531=[!0,1,12,13,14,15,16,18,19,23,24,25,26!]
					^(rotate_left(m[9],30)&3253417984) //3253417984=[!11,12,13,16,17,19,21,22,23,24,30,31!], 128770051=[!0,1,13,14,15,18,19,21,23,24,25,26!]
					^(rotate_left(m[9],29)&1077409792) //1077409792=[!11,12,13,14,15,16,17,18,20,21,30!], 29343746=[!1,14,15,16,17,18,19,20,21,23,24!]
					^(rotate_left(m[9],24)&522240) //522240=[!11,12,13,14,15,16,17,18!], 133693440=[!19,20,21,22,23,24,25,26!]
					^(rotate_left(m[9],31)&5478400) //5478400=[!11,12,15,16,17,20,22!], 10956800=[!12,13,16,17,18,21,23!]
					^(rotate_left(m[9],26)&1234944) //1234944=[!11,12,14,15,17,20!], 79036416=[!17,18,20,21,23,26!]
					^(rotate_left(m[9],28)&6352896) //6352896=[!12,13,14,15,21,22!], 101646336=[!16,17,18,19,25,26!]
					^(rotate_left(m[9],1)&5701632) //5701632=[!16,17,18,20,22!], 2850816=[!15,16,17,19,21!]
					^(rotate_left(m[9],23)&178176) //178176=[!11,12,13,15,17!], 91226112=[!20,21,22,24,26!]
					^(rotate_left(m[9],27)&1908736) //1908736=[!13,16,18,19,20!], 61079552=[!18,21,23,24,25!]
					^(rotate_left(m[9],2)&7602176) //7602176=[!18,20,21,22!], 1900544=[!16,18,19,20!]
					^(rotate_left(m[9],3)&5439488) //5439488=[!16,17,20,22!], 679936=[!13,14,17,19!]
					^(rotate_left(m[9],4)&5373952) //5373952=[!17,20,22!], 335872=[!13,16,18!]
					^(rotate_left(m[9],21)&38912) //38912=[!11,12,15!], 79691776=[!22,23,26!]
					^(rotate_left(m[9],25)&786432) //786432=[!18,19!], 100663296=[!25,26!]
					^(rotate_left(m[9],5)&4194304) //4194304=[!22!], 131072=[!17!]
					^(rotate_left(m[9],6)&4194304) //4194304=[!22!], 65536=[!16!]
					^(rotate_left(m[9],7)&2097152) //2097152=[!21!], 16384=[!14!]
					^(rotate_left(m[9],8)&2097152) //2097152=[!21!], 8192=[!13!]
					^(rotate_left(m[9],18)&4096) //4096=[!12!], 67108864=[!26!]
					^(rotate_left(m[9],20)&8192) //8192=[!13!], 33554432=[!25!]
					^(rotate_left(m[9],22)&4096) //4096=[!12!], 4194304=[!22!]
					;
			metset1precomp[10][15] = metset1precomp[9][15] ^ 0
					^((0-(m[9]&(1<<1)))&1106567172) //1106567172=[!2,13,14,15,18,20,21,22,23,24,30!]
					^((0-((m[9]>>25)&1))&24109056) //24109056=[!13,14,15,16,17,18,19,21,22,24!]
					^((0-((m[9]>>18)&1))&1086111744) //1086111744=[!14,15,18,19,20,21,23,30!]
					^((0-((m[9]>>19)&1))&1102872576) //1102872576=[!15,18,19,20,21,23,24,30!]
					^((0-((m[9]>>21)&1))&28016644) //28016644=[!2,15,16,17,19,21,23,24!]
					^((0-((m[9]>>26)&1))&24174596) //24174596=[!2,13,14,15,20,21,22,24!]
					^((0-((m[9]>>22)&1))&1085390848) //1085390848=[!14,15,16,20,21,23,30!]
					^((0-((m[9]>>17)&1))&11280388) //11280388=[!2,13,18,19,21,23!]
					^((0-((m[9]>>20)&1))&9371652) //9371652=[!2,16,17,18,19,23!]
					^((0-((m[9]>>23)&1))&1082621952) //1082621952=[!15,16,17,18,23,30!]
					^((0-((m[9]>>24)&1))&20332544) //20332544=[!14,17,18,20,21,24!]
					^((0-((m[9]>>31)&1))&25772036) //25772036=[!2,14,16,19,23,24!]
					^((0-(m[9]&(1<<0)))&1078108160) //1078108160=[!13,15,17,22,30!]
					^((0-((m[9]>>16)&1))&9191428) //9191428=[!2,14,18,19,23!]
					^((0-(m[9]&(1<<13)))&16850944) //16850944=[!13,16,24!]
					^((0-(m[9]&(1<<14)))&18939904) //18939904=[!16,21,24!]
					^((0-((m[9]>>15)&1))&2105344) //2105344=[!13,21!]
					;
		}
		Qtp1valsvecptr[t] = Qtp1valsptr;
		if (step_11()) step11ok = true;
		} while (cur != 0);
		if (!step11ok) return step10ok;
	}
	return step10ok;
}
bool step_9()
{
	static bool firsttime = true; if (firsttime) { cout << "t9 " << flush; firsttime = false; }
	const unsigned t = 9;
	UPDATE(t);
	show_performance_data(t);
	bool step9ok = false;
	Qr30[offset+t-2] = rotate_left(Q[offset+t-2],30);
	const uint32 mpartial2 = 0 - sha1_f1(Q[offset+t-1], Qr30[offset+t-2], Qr30[offset+t-3]) - sha1_ac[0] - Qr30[offset+t-4];
	const uint32 metmask = 2013266140;
	for (uint32* Qtvalsptr = Qtp1valsvecptr[t-1]-1; Qtvalsptr >= Qtp1valsvec[t-1]; --Qtvalsptr) {
		Q[offset+t] = *Qtvalsptr;
		m[t-1] = *Qtvalsptr + metpartialvec[t-1];
		const uint32 metset1 = metset1precomp[8][9] ^ 0
				;
		const uint32 Qtp1val = Qvalue[offset+t+1] ^ (Qprev[offset+t+1]&Q[offset+t]);
		const uint32 metset1adj = metset1 ^ ((~Qtp1val) & 2214592545) ^ (xrng64()&67108610);
		const uint32 mpartial = mpartial2 - rotate_left(Q[offset+t],5);
		metpartialvec[t] = mpartial;
		bool didmp = false;
		bool step10ok = false;
		//uint32* Qtp1valsptr = Qtp1valsvec[t];
		uint32 cur = 0; const uint32 curmask = 65011714;// 62914562; // 5 bits
		do { cur -= 1; cur &= curmask;
		uint32 metcur = 0;
		uint32* Qtp1valsptr = Qtp1valsvec[t];
		do {
			m[t] = metcur ^ cur ^ metset1adj;
			metcur -= 1; metcur &= 67108610^curmask; // 19 bits of freedom
			Q[offset+t+1] = m[t] - mpartial;
			if (0 != ((Q[offset+t+1]^Qtp1val)&134217920)) break;
			uint32 Qtp1xorfix = (Q[offset+t+1]^Qtp1val) & 2214592545;
			*(Qtp1valsptr++) = Q[offset+t+1]^Qtp1xorfix;
		} while (metcur != 0);
		//} while (cur != 0);
		if (Qtp1valsptr == Qtp1valsvec[t]) continue;
		step9ok = true;
		if (!didmp) {
			didmp = true;
			metset1precomp[9][10] = metset1precomp[8][10] ^ 0
					;
			metset1precomp[9][11] = metset1precomp[8][11] ^ 0
					;
			metset1precomp[9][12] = metset1precomp[8][12] ^ 0
					^(rotate_left(m[8],0)&2147483648) //2147483648=[!31!], 2147483648=[!31!]
					^(rotate_left(m[8],1)&2147483648) //2147483648=[!31!], 1073741824=[!30!]
					^(rotate_left(m[8],29)&2147483648) //2147483648=[!31!], 4=[!2!]
					;
			metset1precomp[9][13] = metset1precomp[8][13] ^ 0
					^((0-((m[8]>>30)&1))&20316160) //20316160=[!17,18,20,21,24!]
					^((0-(m[8]&(1<<14)))&3538944) //3538944=[!17,18,20,21!]
					^((0-(m[8]&(1<<2)))&1835008) //1835008=[!18,19,20!]
					^((0-(m[8]&(1<<3)))&1441792) //1441792=[!17,18,20!]
					^((0-(m[8]&(1<<11)))&17432576) //17432576=[!17,19,24!]
					^((0-(m[8]&(1<<16)))&19398656) //19398656=[!19,21,24!]
					^((0-((m[8]>>29)&1))&1179648) //1179648=[!17,20!]
					^(rotate_left(m[8],0)&2213150732) //2213150732=[!2,3,17,19,21,22,23,24,25,31!], 2213150732=[!2,3,17,19,21,22,23,24,25,31!]
					^(rotate_left(m[8],30)&13238274) //13238274=[!1,17,19,22,23!], 52953096=[!3,19,21,24,25!]
					^(rotate_left(m[8],31)&18612224) //18612224=[!18,19,20,24!], 37224448=[!19,20,21,25!]
					^(rotate_left(m[8],1)&3670016) //3670016=[!19,20,21!], 1835008=[!18,19,20!]
					^(rotate_left(m[8],29)&1441792) //1441792=[!17,18,20!], 11534336=[!20,21,23!]
					^(rotate_left(m[8],2)&3145728) //3145728=[!20,21!], 786432=[!18,19!]
					^(rotate_left(m[8],4)&16908288) //16908288=[!17,24!], 1056768=[!13,20!]
					^(rotate_left(m[8],25)&17039360) //17039360=[!18,24!], 2181038080=[!25,31!]
					^(rotate_left(m[8],26)&393216) //393216=[!17,18!], 25165824=[!23,24!]
					^(rotate_left(m[8],5)&131072) //131072=[!17!], 4096=[!12!]
					^(rotate_left(m[8],6)&16777216) //16777216=[!24!], 262144=[!18!]
					^(rotate_left(m[8],22)&2097152) //2097152=[!21!], 2147483648=[!31!]
					^(rotate_left(m[8],24)&131072) //131072=[!17!], 33554432=[!25!]
					^(rotate_left(m[8],27)&524288) //524288=[!19!], 16777216=[!24!]
					^(rotate_left(m[8],28)&262144) //262144=[!18!], 4194304=[!22!]
					;
			metset1precomp[9][14] = metset1precomp[8][14] ^ 0
					^((0-(m[8]&(1<<2)))&3227340800) //3227340800=[!12,14,16,18,19,20,22,30,31!]
					^((0-((m[8]>>29)&1))&2151938048) //2151938048=[!11,12,13,14,15,16,17,22,31!]
					^((0-((m[8]>>30)&1))&1081667584) //1081667584=[!12,13,14,15,19,20,21,22,30!]
					^((0-((m[8]>>14)&1))&7718912) //7718912=[!11,14,15,16,18,20,21,22!]
					^((0-((m[8]>>18)&1))&5371904) //5371904=[!11,12,13,14,15,16,20,22!]
					^((0-((m[8]>>20)&1))&5728256) //5728256=[!11,13,14,16,17,18,20,22!]
					^((0-(m[8]&(1<<3)))&7520256) //7520256=[!14,15,17,20,21,22!]
					^((0-((m[8]>>19)&1))&7385088) //7385088=[!12,13,15,20,21,22!]
					^((0-((m[8]>>21)&1))&6350848) //6350848=[!11,13,14,15,21,22!]
					^((0-(m[8]&(1<<11)))&2299904) //2299904=[!11,12,16,17,21!]
					^((0-((m[8]>>16)&1))&2564096) //2564096=[!13,16,17,18,21!]
					^((0-((m[8]>>22)&1))&5408768) //5408768=[!11,15,17,20,22!]
					^((0-((m[8]>>23)&1))&3172352) //3172352=[!11,13,14,20,21!]
					^((0-((m[8]>>31)&1))&669696) //669696=[!11,12,13,17,19!]
					^((0-((m[8]>>24)&1))&602112) //602112=[!12,13,16,19!]
					^((0-((m[8]>>25)&1))&4231168) //4231168=[!12,15,22!]
					^((0-(m[8]&(1<<12)))&69632) //69632=[!12,16!]
					^((0-((m[8]>>15)&1))&6144) //6144=[!11,12!]
					^(rotate_left(m[8],31)&2155231232) //2155231232=[!11,12,13,17,18,20,21,22,31!], 15495169=[!0,12,13,14,18,19,21,22,23!]
					^(rotate_left(m[8],30)&1073743872) //1073743872=[!11,30!], 8193=[!0,13!]
					^(rotate_left(m[8],2)&2048) //2048=[!11!], 512=[!9!]
					^(rotate_left(m[8],3)&65536) //65536=[!16!], 8192=[!13!]
					;
			metset1precomp[9][15] = metset1precomp[8][15] ^ 0
					^((0-(m[8]&(1<<3)))&27238400) //27238400=[!13,15,16,17,18,19,20,23,24!]
					^((0-((m[8]>>2)&1))&29614081) //29614081=[!0,13,14,15,16,17,22,23,24!]
					^((0-((m[8]>>22)&1))&1099915264) //1099915264=[!13,14,16,17,18,19,23,24,30!]
					^((0-((m[8]>>19)&1))&27992068) //27992068=[!2,13,16,17,19,21,23,24!]
					^((0-((m[8]>>25)&1))&1076862976) //1076862976=[!13,15,16,17,18,19,21,30!]
					^((0-((m[8]>>29)&1))&2023428) //2023428=[!2,13,14,15,17,18,19,20!]
					^((0-((m[8]>>31)&1))&24002564) //24002564=[!2,14,17,18,19,21,22,24!]
					^((0-((m[8]>>14)&1))&26034180) //26034180=[!2,14,16,18,19,23,24!]
					^((0-((m[8]>>16)&1))&1093730308) //1093730308=[!2,16,20,21,24,30!]
					^((0-((m[8]>>18)&1))&1084030976) //1084030976=[!16,18,19,20,23,30!]
					^((0-((m[8]>>23)&1))&25788420) //25788420=[!2,15,16,19,23,24!]
					^((0-((m[8]>>30)&1))&13746176) //13746176=[!14,15,16,20,22,23!]
					^((0-((m[8]>>20)&1))&10534916) //10534916=[!2,14,15,21,23!]
					^((0-((m[8]>>21)&1))&1101266944) //1101266944=[!18,21,23,24,30!]
					^((0-((m[8]>>24)&1))&4833280) //4833280=[!14,15,16,19,22!]
					^((0-(m[8]&(1<<11)))&16850944) //16850944=[!13,16,24!]
					^((0-(m[8]&(1<<12)))&2105344) //2105344=[!13,21!]
					^((0-(m[8]&(1<<13)))&2105344) //2105344=[!13,21!]
					^(rotate_left(m[8],31)&2179194880) //2179194880=[!13,14,15,16,17,21,22,23,24,31!], 63422465=[!0,14,15,16,17,18,22,23,24,25!]
					^(rotate_left(m[8],30)&40960) //40960=[!13,15!], 163840=[!15,17!]
					^(rotate_left(m[8],13)&8192) //8192=[!13!], 1=[!0!]
					;
		}
		Qtp1valsvecptr[t] = Qtp1valsptr;
		if (step_10()) step10ok = true;
		} while (cur != 0);
		if (!step10ok) return step9ok;
	}
	return step9ok;
}
bool step_8()
{
	static bool firsttime = true; if (firsttime) { cout << "t8 " << flush; firsttime = false; }
	const unsigned t = 8;
	UPDATE(t);
	show_performance_data(t);
	bool step8ok = false;
	Qr30[offset+t-2] = rotate_left(Q[offset+t-2],30);
	const uint32 mpartial2 = 0 - sha1_f1(Q[offset+t-1], Qr30[offset+t-2], Qr30[offset+t-3]) - sha1_ac[0] - Qr30[offset+t-4];
	const uint32 metmask = 469762050;
	for (uint32* Qtvalsptr = Qtp1valsvecptr[t-1]-1; Qtvalsptr >= Qtp1valsvec[t-1]; --Qtvalsptr) {
		Q[offset+t] = *Qtvalsptr;
		m[t-1] = *Qtvalsptr + metpartialvec[t-1];
		const uint32 metset1 = metset1precomp[7][8] ^ 0
				;
		const uint32 Qtp1val = Qvalue[offset+t+1] ^ (Qprev[offset+t+1]&Q[offset+t]) ^ ((~metset1) & 402653186) ^ (xrng64()&3288333445);
		const uint32 mpartial = mpartial2 - rotate_left(Q[offset+t],5);
		metpartialvec[t] = mpartial;
		bool didmp = false;
		//uint32* Qtp1valsptr = Qtp1valsvec[t];
		uint32 cur = 0; const uint32 curmask = 66846720;//65011712; // 5 bits
		do { cur -= 1; cur &= curmask;
		uint32* Qtp1valsptr = Qtp1valsvec[t];
		uint32 Qtp1cur = 0;
		do {
			Q[offset+t+1] = Qtp1cur ^ cur ^ Qtp1val;
			Qtp1cur -= 1; Qtp1cur &= 3288333445^curmask; // 21 bits of freedom
			m[t] = Q[offset+t+1] + mpartial;
			if (0 != ((m[t]^metset1)&67108864)) break;
			uint32 metxorfix = (m[t]^metset1) & 402653186;
			*(Qtp1valsptr++) = Q[offset+t+1]^metxorfix;
		} while (Qtp1cur != 0);
		//} while (cur != 0);
		if (Qtp1valsptr == Qtp1valsvec[t]) continue;
		step8ok = true;
		if (!didmp) {
			didmp = true;
			metset1precomp[8][9] = metset1precomp[7][9] ^ 0
					;
			metset1precomp[8][10] = metset1precomp[7][10] ^ 0
					;
			metset1precomp[8][11] = metset1precomp[7][11] ^ 0
					;
			metset1precomp[8][12] = metset1precomp[7][12] ^ 0
					;
			metset1precomp[8][13] = metset1precomp[7][13] ^ 0
					^((0-((m[7]>>31)&1))&19660800) //19660800=[!18,19,21,24!]
					^((0-(m[7]&(1<<0)))&2359296) //2359296=[!18,21!]
					^((0-(m[7]&(1<<15)))&17301504) //17301504=[!19,24!]
					^(rotate_left(m[7],2)&20578304) //20578304=[!17,19,20,21,24!], 5144576=[!15,17,18,19,22!]
					^(rotate_left(m[7],29)&3932160) //3932160=[!18,19,20,21!], 31457280=[!21,22,23,24!]
					^(rotate_left(m[7],31)&18219008) //18219008=[!17,18,20,24!], 36438016=[!18,19,21,25!]
					^(rotate_left(m[7],0)&17563648) //17563648=[!18,19,24!], 17563648=[!18,19,24!]
					^(rotate_left(m[7],1)&19922944) //19922944=[!20,21,24!], 9961472=[!19,20,23!]
					^(rotate_left(m[7],30)&3670016) //3670016=[!19,20,21!], 14680064=[!21,22,23!]
					^(rotate_left(m[7],3)&18874368) //18874368=[!21,24!], 2359296=[!18,21!]
					^(rotate_left(m[7],5)&16777216) //16777216=[!24!], 524288=[!19!]
					^(rotate_left(m[7],7)&16777216) //16777216=[!24!], 131072=[!17!]
					^(rotate_left(m[7],25)&131072) //131072=[!17!], 16777216=[!24!]
					^(rotate_left(m[7],27)&1048576) //1048576=[!20!], 33554432=[!25!]
					;
			metset1precomp[8][14] = metset1precomp[7][14] ^ 0
					^((0-(m[7]&(1<<0)))&2151045120) //2151045120=[!11,12,14,17,18,20,21,31!]
					^((0-((m[7]>>23)&1))&7755776) //7755776=[!11,12,14,17,18,20,21,22!]
					^((0-((m[7]>>31)&1))&1075113984) //1075113984=[!12,13,14,15,18,20,30!]
					^((0-((m[7]>>18)&1))&7643136) //7643136=[!13,15,18,20,21,22!]
					^((0-((m[7]>>19)&1))&5533696) //5533696=[!12,13,14,18,20,22!]
					^((0-((m[7]>>21)&1))&5287936) //5287936=[!12,13,15,20,22!]
					^((0-((m[7]>>25)&1))&126976) //126976=[!12,13,14,15,16!]
					^((0-((m[7]>>15)&1))&2297856) //2297856=[!12,16,17,21!]
					^((0-((m[7]>>22)&1))&4331520) //4331520=[!11,12,17,22!]
					^((0-((m[7]>>24)&1))&301056) //301056=[!11,12,15,18!]
					^((0-(m[7]&(1<<1)))&77824) //77824=[!12,13,16!]
					^((0-((m[7]>>17)&1))&2230272) //2230272=[!11,17,21!]
					^(rotate_left(m[7],28)&3393536) //3393536=[!11,14,15,16,17,20,21!], 54296576=[!15,18,19,20,21,24,25!]
					^(rotate_left(m[7],30)&8974336) //8974336=[!12,13,14,15,19,23!], 35897344=[!14,15,16,17,21,25!]
					^(rotate_left(m[7],23)&2048) //2048=[!11!], 1048576=[!20!]
					^(rotate_left(m[7],29)&2048) //2048=[!11!], 16384=[!14!]
					;
			metset1precomp[8][15] = metset1precomp[7][15] ^ 0
					^((0-(m[7]&(1<<0)))&2174197764) //2174197764=[!2,13,15,16,17,18,20,23,24,31!]
					^((0-((m[7]>>23)&1))&15622148) //15622148=[!2,13,14,17,18,19,21,22,23!]
					^((0-((m[7]>>18)&1))&26165252) //26165252=[!2,14,16,17,18,19,23,24!]
					^((0-((m[7]>>25)&1))&1077518340) //1077518340=[!2,13,15,16,19,20,21,30!]
					^((0-((m[7]>>21)&1))&1085046784) //1085046784=[!15,18,19,21,23,30!]
					^((0-((m[7]>>22)&1))&1084030976) //1084030976=[!16,18,19,20,23,30!]
					^((0-((m[7]>>31)&1))&9912320) //9912320=[!14,16,17,18,20,23!]
					^((0-((m[7]>>19)&1))&8929284) //8929284=[!2,14,19,23!]
					^((0-((m[7]>>24)&1))&2629636) //2629636=[!2,13,19,21!]
					^((0-((m[7]>>15)&1))&16850944) //16850944=[!13,16,24!]
					^((0-((m[7]>>20)&1))&1074790404) //1074790404=[!2,20,30!]
					^((0-(m[7]&(1<<17)))&18874368) //18874368=[!21,24!]
					^(rotate_left(m[7],31)&581633) //581633=[!0,13,14,15,19!], 1163266=[!1,14,15,16,20!]
					^(rotate_left(m[7],20)&2097152) //2097152=[!21!], 2=[!1!]
					;
		}
		Qtp1valsvecptr[t] = Qtp1valsptr;
		step_9();
		} while (cur != 0);
	}
	return step8ok;
}
bool step_7()
{
	static bool firsttime = true; if (firsttime) { cout << "t7 " << endl; firsttime = false; }
	const unsigned t = 7;
	UPDATE(t);
	show_performance_data(t);
	bool step7ok = false;
	Qr30[offset+t-2] = rotate_left(Q[offset+t-2],30);
	const uint32 mpartial2 = 0 - sha1_f1(Q[offset+t-1], Qr30[offset+t-2], Qr30[offset+t-3]) - sha1_ac[0] - Qr30[offset+t-4];
	const uint32 metmask = 2080390172;
	for (uint32* Qtvalsptr = Qtp1valsvecptr[t-1]-1; Qtvalsptr >= Qtp1valsvec[t-1]; --Qtvalsptr) {
		Q[offset+t] = *Qtvalsptr;
		m[t-1] = *Qtvalsptr + metpartialvec[t-1];
		const uint32 metset1 = metset1precomp[6][7] ^ 0
				;
		const uint32 Qtp1val = Qvalue[offset+t+1] ^ (Qprev[offset+t+1]&Q[offset+t]);
		const uint32 metset1adj = metset1 ^ ((~Qtp1val) & 2147483744) ^ (xrng64()&67093379);
		const uint32 mpartial = mpartial2 - rotate_left(Q[offset+t],5);
		metpartialvec[t] = mpartial;
		bool didmp = false;
		//uint32* Qtp1valsptr = Qtp1valsvec[t];
		uint32 cur = 0; const uint32 curmask = 65011715; // 7 bits
		do { cur -= 1; cur &= curmask;
		uint32 metcur = 0;
		uint32* Qtp1valsptr = Qtp1valsvec[t];
		do {
			m[t] = metcur ^ cur ^ metset1adj;
			metcur -= 1; metcur &= 67093379^curmask; // 17 bits of freedom
			Q[offset+t+1] = m[t] - mpartial;
			if (0 != ((Q[offset+t+1]^Qtp1val)&872415260)) break;
			uint32 Qtp1xorfix = (Q[offset+t+1]^Qtp1val) & 2147483744;
			*(Qtp1valsptr++) = Q[offset+t+1]^Qtp1xorfix;
		} while (metcur != 0);
		//} while (cur != 0);
		if (Qtp1valsptr == Qtp1valsvec[t]) continue;
		step7ok = true;
		if (!didmp) {
			didmp = true;
			metset1precomp[7][8] = metset1precomp[6][8] ^ 0
					;
			metset1precomp[7][9] = metset1precomp[6][9] ^ 0
					;
			metset1precomp[7][10] = metset1precomp[6][10] ^ 0
					;
			metset1precomp[7][11] = metset1precomp[6][11] ^ 0
					;
			metset1precomp[7][12] = metset1precomp[6][12] ^ 0
					^(rotate_left(m[6],31)&2147483648) //2147483648=[!31!], 1=[!0!]
					;
			metset1precomp[7][13] = metset1precomp[6][13] ^ 0
					^((0-((m[6]>>21)&1))&20316160) //20316160=[!17,18,20,21,24!]
					^((0-((m[6]>>30)&1))&19791872) //19791872=[!17,18,19,21,24!]
					^((0-(m[6]&(1<<18)))&18612224) //18612224=[!18,19,20,24!]
					^((0-((m[6]>>25)&1))&19660800) //19660800=[!18,19,21,24!]
					^((0-(m[6]&(1<<0)))&19005440) //19005440=[!17,21,24!]
					^((0-(m[6]&(1<<1)))&19922944) //19922944=[!20,21,24!]
					^((0-((m[6]>>22)&1))&17432576) //17432576=[!17,19,24!]
					^((0-((m[6]>>31)&1))&17432576) //17432576=[!17,19,24!]
					^((0-(m[6]&(1<<13)))&17301504) //17301504=[!19,24!]
					^(rotate_left(m[6],30)&2161377280) //2161377280=[!18,20,22,23,31!], 55574530=[!1,20,22,24,25!]
					^(rotate_left(m[6],4)&1703936) //1703936=[!17,19,20!], 106496=[!13,15,16!]
					^(rotate_left(m[6],5)&18874368) //18874368=[!21,24!], 589824=[!16,19!]
					^(rotate_left(m[6],0)&524288) //524288=[!19!], 524288=[!19!]
					^(rotate_left(m[6],2)&262144) //262144=[!18!], 65536=[!16!]
					^(rotate_left(m[6],3)&131072) //131072=[!17!], 16384=[!14!]
					^(rotate_left(m[6],9)&16777216) //16777216=[!24!], 32768=[!15!]
					^(rotate_left(m[6],26)&131072) //131072=[!17!], 8388608=[!23!]
					^(rotate_left(m[6],29)&131072) //131072=[!17!], 1048576=[!20!]
					;
			metset1precomp[7][14] = metset1precomp[6][14] ^ 0
					^((0-((m[6]>>16)&1))&7632896) //7632896=[!11,12,13,14,18,20,21,22!]
					^((0-((m[6]>>18)&1))&5371904) //5371904=[!11,12,13,14,15,16,20,22!]
					^((0-(m[6]&(1<<0)))&1074489344) //1074489344=[!11,13,14,16,17,19,30!]
					^((0-(m[6]&(1<<1)))&3226050560) //3226050560=[!13,15,16,19,22,30,31!]
					^((0-((m[6]>>21)&1))&4642816) //4642816=[!11,12,14,15,17,18,22!]
					^((0-((m[6]>>25)&1))&3467264) //3467264=[!11,13,14,15,18,20,21!]
					^((0-((m[6]>>19)&1))&2316288) //2316288=[!11,12,14,16,17,21!]
					^((0-((m[6]>>30)&1))&2148833280) //2148833280=[!11,12,15,18,20,31!]
					^((0-((m[6]>>22)&1))&96256) //96256=[!11,12,13,14,16!]
					^((0-((m[6]>>24)&1))&581632) //581632=[!13,14,15,19!]
					^((0-(m[6]&(1<<13)))&2293760) //2293760=[!16,17,21!]
					^((0-((m[6]>>14)&1))&71680) //71680=[!11,12,16!]
					^((0-((m[6]>>15)&1))&2230272) //2230272=[!11,17,21!]
					^((0-((m[6]>>20)&1))&100352) //100352=[!11,15,16!]
					^((0-((m[6]>>31)&1))&2232320) //2232320=[!12,17,21!]
					^((0-((m[6]>>23)&1))&49152) //49152=[!14,15!]
					^(rotate_left(m[6],31)&3251464193) //3251464193=[!0,11,13,14,16,18,19,22,23,24,30,31!], 2207961091=[!0,1,12,14,15,17,19,20,23,24,25,31!]
					^(rotate_left(m[6],0)&2048) //2048=[!11!], 2048=[!11!]
					;
			metset1precomp[7][15] = metset1precomp[6][15] ^ 0
					^((0-(m[6]&(1<<0)))&1097490432) //1097490432=[!13,14,17,19,21,22,24,30!]
					^((0-((m[6]>>16)&1))&28131332) //28131332=[!2,14,16,18,19,21,23,24!]
					^((0-((m[6]>>30)&1))&1083400196) //1083400196=[!2,13,14,16,17,20,23,30!]
					^((0-((m[6]>>25)&1))&1094770692) //1094770692=[!2,13,14,15,22,24,30!]
					^((0-(m[6]&(1<<1)))&22323200) //22323200=[!13,15,18,20,22,24!]
					^((0-((m[6]>>18)&1))&1083998208) //1083998208=[!15,18,19,20,23,30!]
					^((0-((m[6]>>21)&1))&11026436) //11026436=[!2,14,19,21,23!]
					^((0-((m[6]>>31)&1))&18948096) //18948096=[!13,16,21,24!]
					^((0-(m[6]&(1<<13)))&16850944) //16850944=[!13,16,24!]
					^((0-(m[6]&(1<<15)))&18939904) //18939904=[!16,21,24!]
					^((0-((m[6]>>23)&1))&1075838980) //1075838980=[!2,21,30!]
					^((0-((m[6]>>24)&1))&57344) //57344=[!13,14,15!]
					^((0-((m[6]>>14)&1))&2105344) //2105344=[!13,21!]
					^((0-((m[6]>>20)&1))&2105344) //2105344=[!13,21!]
					^(rotate_left(m[6],28)&2088960) //2088960=[!13,14,15,16,17,18,19,20!], 33423360=[!17,18,19,20,21,22,23,24!]
					^(rotate_left(m[6],27)&1032192) //1032192=[!14,15,16,17,18,19!], 33030144=[!19,20,21,22,23,24!]
					^(rotate_left(m[6],29)&671744) //671744=[!14,17,19!], 5373952=[!17,20,22!]
					^(rotate_left(m[6],26)&73728) //73728=[!13,16!], 4718592=[!19,22!]
					^(rotate_left(m[6],2)&16777216) //16777216=[!24!], 4194304=[!22!]
					^(rotate_left(m[6],5)&16777216) //16777216=[!24!], 524288=[!19!]
					;
		}
		Qtp1valsvecptr[t] = Qtp1valsptr;
		try { // restart from step 7, after 4 tries restart from step 0
		step_8();
		} catch (std::exception& e) { 
			cout << "step7: " << e.what() << endl; 
			if (time_avg[15] || time_avg[40]) {
				cout << "Restart after step 15: tunnel changes might corrupt current workingstate!" << endl;
				exit(0);
			}
			static unsigned throwcnt = 0;
			if (((++throwcnt)&3)==0)
				throw;
		}
		} while (cur != 0);
	}
	return step7ok;
}
bool step_6()
{
	static bool firsttime = true; if (firsttime) { cout << "t6 " << flush; firsttime = false; }
	const unsigned t = 6;
	UPDATE(t);
	show_performance_data(t);
	bool step6ok = false;
	Qr30[offset+t-2] = rotate_left(Q[offset+t-2],30);
	const uint32 mpartial2 = 0 - sha1_f1(Q[offset+t-1], Qr30[offset+t-2], Qr30[offset+t-3]) - sha1_ac[0] - Qr30[offset+t-4];
	const uint32 metmask = 1006634012;
	for (uint32* Qtvalsptr = Qtp1valsvecptr[t-1]-1; Qtvalsptr >= Qtp1valsvec[t-1]; --Qtvalsptr) {
		Q[offset+t] = *Qtvalsptr;
		m[t-1] = *Qtvalsptr + metpartialvec[t-1];
		const uint32 metset1 = metset1precomp[5][6] ^ 0
				;
		const uint32 Qtp1val = Qvalue[offset+t+1] ^ (Qprev[offset+t+1]&Q[offset+t]) ^ ((~metset1) & 939525128) ^ (xrng64()&67107331);
		const uint32 mpartial = mpartial2 - rotate_left(Q[offset+t],5);
		metpartialvec[t] = mpartial;
		bool didmp = false;
		bool step7ok = false;
		//uint32* Qtp1valsptr = Qtp1valsvec[t];
		uint32 cur = 0; const uint32 curmask = 65011715; // 7 bits
		do { cur -= 1; cur &= curmask;
		uint32* Qtp1valsptr = Qtp1valsvec[t];
		uint32 Qtp1cur = 0;
		do {
			Q[offset+t+1] = Qtp1cur ^ cur ^ Qtp1val;
			Qtp1cur -= 1; Qtp1cur &= 67107331^curmask; // 18 bits of freedom
			m[t] = Q[offset+t+1] + mpartial;
			if (0 != ((m[t]^metset1)&67108884)) break;
			uint32 metxorfix = (m[t]^metset1) & 939525128;
			*(Qtp1valsptr++) = Q[offset+t+1]^metxorfix;
		} while (Qtp1cur != 0);
		//} while (cur != 0);
		if (Qtp1valsptr == Qtp1valsvec[t]) continue;
		step6ok = true;
		if (!didmp) {
			didmp = true;
			metset1precomp[6][7] = metset1precomp[5][7] ^ 0
					^(rotate_left(m[5],0)&268435456) //268435456=[!28!], 268435456=[!28!]
					;
			metset1precomp[6][8] = metset1precomp[5][8] ^ 0
					;
			metset1precomp[6][9] = metset1precomp[5][9] ^ 0
					;
			metset1precomp[6][10] = metset1precomp[5][10] ^ 0
					;
			metset1precomp[6][11] = metset1precomp[5][11] ^ 0
					^(rotate_left(m[5],0)&8) //8=[!3!], 8=[!3!]
					;
			metset1precomp[6][12] = metset1precomp[5][12] ^ 0
					^(rotate_left(m[5],1)&2147483648) //2147483648=[!31!], 1073741824=[!30!]
					^(rotate_left(m[5],31)&2147483648) //2147483648=[!31!], 1=[!0!]
					;
			metset1precomp[6][13] = metset1precomp[5][13] ^ 0
					^((0-(m[5]&(1<<15)))&20709376) //20709376=[!18,19,20,21,24!]
					^((0-((m[5]>>30)&1))&20054016) //20054016=[!17,20,21,24!]
					^((0-(m[5]&(1<<0)))&19398656) //19398656=[!19,21,24!]
					^((0-(m[5]&(1<<3)))&1441792) //1441792=[!17,18,20!]
					^((0-(m[5]&(1<<13)))&17432576) //17432576=[!17,19,24!]
					^((0-((m[5]>>31)&1))&1703936) //1703936=[!17,19,20!]
					^(rotate_left(m[5],31)&2328363010) //2328363010=[!1,19,22,23,25,27,31!], 361758725=[!0,2,20,23,24,26,28!]
					^(rotate_left(m[5],1)&20316160) //20316160=[!17,18,20,21,24!], 10158080=[!16,17,19,20,23!]
					^(rotate_left(m[5],30)&3014658) //3014658=[!1,17,18,19,21!], 12058632=[!3,19,20,21,23!]
					^(rotate_left(m[5],25)&19267584) //19267584=[!17,18,21,24!], 2466250752=[!24,25,28,31!]
					^(rotate_left(m[5],0)&1703936) //1703936=[!17,19,20!], 1703936=[!17,19,20!]
					^(rotate_left(m[5],3)&18350080) //18350080=[!19,20,24!], 2293760=[!16,17,21!]
					^(rotate_left(m[5],5)&16908290) //16908290=[!1,17,24!], 268963840=[!12,19,28!]
					^(rotate_left(m[5],29)&1835008) //1835008=[!18,19,20!], 14680064=[!21,22,23!]
					^(rotate_left(m[5],2)&18874368) //18874368=[!21,24!], 4718592=[!19,22!]
					^(rotate_left(m[5],28)&1572864) //1572864=[!19,20!], 25165824=[!23,24!]
					^(rotate_left(m[5],8)&16777216) //16777216=[!24!], 65536=[!16!]
					^(rotate_left(m[5],19)&2097152) //2097152=[!21!], 4=[!2!]
					^(rotate_left(m[5],23)&524288) //524288=[!19!], 268435456=[!28!]
					^(rotate_left(m[5],27)&524288) //524288=[!19!], 16777216=[!24!]
					;
			metset1precomp[6][14] = metset1precomp[5][14] ^ 0
					^((0-((m[5]>>20)&1))&7725056) //7725056=[!13,14,15,16,18,20,21,22!]
					^((0-(m[5]&(1<<3)))&7520256) //7520256=[!14,15,17,20,21,22!]
					^((0-((m[5]>>15)&1))&5677056) //5677056=[!13,15,17,18,20,22!]
					^((0-(m[5]&(1<<2)))&415744) //415744=[!11,12,14,17,18!]
					^((0-((m[5]>>31)&1))&6318080) //6318080=[!11,13,14,21,22!]
					^((0-(m[5]&(1<<0)))&376832) //376832=[!14,15,16,18!]
					^((0-((m[5]>>30)&1))&69632) //69632=[!12,16!]
					^(rotate_left(m[5],31)&1081366528) //1081366528=[!11,12,14,18,20,21,22,30!], 2162733056=[!12,13,15,19,21,22,23,31!]
					^(rotate_left(m[5],21)&2807808) //2807808=[!11,12,14,15,17,19,21!], 1455423489=[!0,22,23,25,26,28,30!]
					^(rotate_left(m[5],29)&7428096) //7428096=[!11,12,14,16,20,21,22!], 59424768=[!14,15,17,19,23,24,25!]
					^(rotate_left(m[5],26)&1226752) //1226752=[!11,12,13,15,17,20!], 78512128=[!17,18,19,21,23,26!]
					^(rotate_left(m[5],27)&3620864) //3620864=[!14,16,17,18,20,21!], 115867648=[!19,21,22,23,25,26!]
					^(rotate_left(m[5],24)&4622336) //4622336=[!11,15,17,18,22!], 1183318016=[!19,23,25,26,30!]
					^(rotate_left(m[5],28)&2650112) //2650112=[!12,13,14,19,21!], 42401792=[!16,17,18,23,25!]
					^(rotate_left(m[5],1)&5376000) //5376000=[!11,17,20,22!], 2688000=[!10,16,19,21!]
					^(rotate_left(m[5],30)&4423680) //4423680=[!15,16,17,22!], 17694720=[!17,18,19,24!]
					^(rotate_left(m[5],0)&1073811456) //1073811456=[!12,16,30!], 1073811456=[!12,16,30!]
					^(rotate_left(m[5],3)&5308416) //5308416=[!16,20,22!], 663552=[!13,17,19!]
					^(rotate_left(m[5],4)&2293760) //2293760=[!16,17,21!], 143360=[!12,13,17!]
					^(rotate_left(m[5],19)&38912) //38912=[!11,12,15!], 318767104=[!24,25,28!]
					^(rotate_left(m[5],23)&200704) //200704=[!12,16,17!], 102760448=[!21,25,26!]
					^(rotate_left(m[5],25)&2179072) //2179072=[!14,16,21!], 278921216=[!21,23,28!]
					^(rotate_left(m[5],5)&6291456) //6291456=[!21,22!], 196608=[!16,17!]
					^(rotate_left(m[5],20)&20480) //20480=[!12,14!], 83886080=[!24,26!]
					^(rotate_left(m[5],8)&2097152) //2097152=[!21!], 8192=[!13!]
					^(rotate_left(m[5],22)&262144) //262144=[!18!], 268435456=[!28!]
					;
			metset1precomp[6][15] = metset1precomp[5][15] ^ 0
					^((0-(m[5]&(1<<3)))&27238400) //27238400=[!13,15,16,17,18,19,20,23,24!]
					^((0-((m[5]>>30)&1))&1096114180) //1096114180=[!2,13,14,16,18,20,22,24,30!]
					^((0-((m[5]>>28)&1))&1089495044) //1089495044=[!2,13,14,20,21,22,23,30!]
					^((0-(m[5]&(1<<2)))&1075240960) //1075240960=[!13,14,15,17,18,20,30!]
					^((0-((m[5]>>24)&1))&1092517888) //1092517888=[!15,17,18,19,20,24,30!]
					^((0-((m[5]>>25)&1))&1077616640) //1077616640=[!13,16,17,19,20,21,30!]
					^((0-(m[5]&(1<<0)))&20324352) //20324352=[!13,17,18,20,21,24!]
					^((0-((m[5]>>23)&1))&9273348) //9273348=[!2,15,16,18,19,23!]
					^((0-(m[5]&(1<<17)))&1099694080) //1099694080=[!18,19,23,24,30!]
					^((0-((m[5]>>19)&1))&11026436) //11026436=[!2,14,19,21,23!]
					^((0-((m[5]>>20)&1))&18956292) //18956292=[!2,14,16,21,24!]
					^((0-((m[5]>>22)&1))&1090617348) //1090617348=[!2,15,16,24,30!]
					^((0-((m[5]>>31)&1))&18743296) //18743296=[!17,18,19,20,24!]
					^((0-((m[5]>>21)&1))&1082408960) //1082408960=[!14,18,23,30!]
					^((0-((m[5]>>26)&1))&8585220) //8585220=[!2,16,17,23!]
					^((0-((m[5]>>15)&1))&8912900) //8912900=[!2,19,23!]
					^((0-((m[5]>>16)&1))&16850944) //16850944=[!13,16,24!]
					^((0-(m[5]&(1<<12)))&2105344) //2105344=[!13,21!]
					^((0-(m[5]&(1<<13)))&16785408) //16785408=[!13,24!]
					^(rotate_left(m[5],31)&2204278785) //2204278785=[!0,13,15,17,21,22,24,25,31!], 113590275=[!0,1,14,16,18,22,23,25,26!]
					^(rotate_left(m[5],30)&1102848000) //1102848000=[!13,18,19,20,21,23,24,30!], 116424705=[!0,15,20,21,22,23,25,26!]
					^(rotate_left(m[5],3)&11862020) //11862020=[!2,16,18,20,21,23!], 2148966400=[!13,15,17,18,20,31!]
					^(rotate_left(m[5],27)&8192) //8192=[!13!], 262144=[!18!]
					;
		}
		Qtp1valsvecptr[t] = Qtp1valsptr;
		if (step_7()) step7ok = true;
		} while (cur != 0);
		if (!step7ok) return false;
	}
	return step6ok;
}
bool step_5()
{
	static bool firsttime = true; if (firsttime) { cout << "t5 " << flush; firsttime = false; }
	const unsigned t = 5;
	UPDATE(t);
	show_performance_data(t);
	bool step5ok = false;
	Qr30[offset+t-2] = rotate_left(Q[offset+t-2],30);
	const uint32 mpartial2 = 0 - sha1_f1(Q[offset+t-1], Qr30[offset+t-2], Qr30[offset+t-3]) - sha1_ac[0] - Qr30[offset+t-4];
	const uint32 metmask = 671088656;
	for (uint32* Qtvalsptr = Qtp1valsvecptr[t-1]-1; Qtvalsptr >= Qtp1valsvec[t-1]; --Qtvalsptr) {
		Q[offset+t] = *Qtvalsptr;
		m[t-1] = *Qtvalsptr + metpartialvec[t-1];
		const uint32 metset1 = metset1precomp[4][5] ^ 0
				;
		const uint32 Qtp1val = Qvalue[offset+t+1] ^ (Qprev[offset+t+1]&Q[offset+t]) ^ ((~metset1) & 671088640) ^ (xrng64()&2281699337);
		const uint32 mpartial = mpartial2 - rotate_left(Q[offset+t],5);
		metpartialvec[t] = mpartial;
		bool didmp = false;
		bool step6ok = false;
		//uint32* Qtp1valsptr = Qtp1valsvec[t];
		uint32 cur = 0; const uint32 curmask = 125829129;// 9; // 2 bits
		do { cur -= 1; cur &= curmask;
		uint32* Qtp1valsptr = Qtp1valsvec[t];
		uint32 Qtp1cur = 0;
		do {
			Q[offset+t+1] = Qtp1cur ^ cur ^ Qtp1val;
			Qtp1cur -= 1; Qtp1cur &= 2281699337^curmask; // 19 bits of freedom
			m[t] = Q[offset+t+1] + mpartial;
			if (0 != ((m[t]^metset1)&16)) break;
			if ((m[t]&992)==0) continue;
			uint32 metxorfix = (m[t]^metset1) & 671088640;
			*(Qtp1valsptr++) = Q[offset+t+1]^metxorfix;
		} while (Qtp1cur != 0);
		//} while (cur != 0);
		if (Qtp1valsptr == Qtp1valsvec[t]) continue;
		step5ok = true;
		if (!didmp) {
			didmp = true;
			metset1precomp[5][6] = metset1precomp[4][6] ^ 0;
			metset1precomp[5][7] = metset1precomp[4][7] ^ 0;
			metset1precomp[5][8] = metset1precomp[4][8] ^ 0;
			metset1precomp[5][9] = metset1precomp[4][9] ^ 0;
			metset1precomp[5][10] = metset1precomp[4][10] ^ 0;
			metset1precomp[5][11] = metset1precomp[4][11] ^ 0;
			metset1precomp[5][12] = metset1precomp[4][12] ^ 0
					^(rotate_left(m[4],1)&2147483648) //2147483648=[!31!], 1073741824=[!30!]
					^(rotate_left(m[4],29)&2147483648) //2147483648=[!31!], 4=[!2!]
					^(rotate_left(m[4],31)&2147483648) //2147483648=[!31!], 1=[!0!]
					;
			metset1precomp[5][13] = metset1precomp[4][13] ^ 0
					^((0-((m[4]>>19)&1))&20709376) //20709376=[!18,19,20,21,24!]
					^((0-((m[4]>>21)&1))&18743296) //18743296=[!17,18,19,20,24!]
					^((0-((m[4]>>20)&1))&18612224) //18612224=[!18,19,20,24!]
					^((0-(m[4]&(1<<0)))&3276800) //3276800=[!17,20,21!]
					^((0-((m[4]>>31)&1))&3407872) //3407872=[!18,20,21!]
					^((0-((m[4]>>30)&1))&1310720) //1310720=[!18,20!]
					^(rotate_left(m[4],2)&17956864) //17956864=[!17,20,24!], 4489216=[!15,18,22!]
					^(rotate_left(m[4],28)&1835008) //1835008=[!18,19,20!], 29360128=[!22,23,24!]
					^(rotate_left(m[4],29)&2149056512) //2149056512=[!19,20,31!], 12582916=[!2,22,23!]
					^(rotate_left(m[4],0)&393216) //393216=[!17,18!], 393216=[!17,18!]
					^(rotate_left(m[4],27)&1572864) //1572864=[!19,20!], 50331648=[!24,25!]
					^(rotate_left(m[4],3)&2097152) //2097152=[!21!], 262144=[!18!]
					^(rotate_left(m[4],25)&131072) //131072=[!17!], 16777216=[!24!]
					^(rotate_left(m[4],30)&2097152) //2097152=[!21!], 8388608=[!23!]
					;
			metset1precomp[5][14] = metset1precomp[4][14] ^ 0
					^((0-((m[4]>>24)&1))&1570816) //1570816=[!11,12,13,14,15,16,17,18,20!]
					^((0-((m[4]>>31)&1))&7718912) //7718912=[!11,14,15,16,18,20,21,22!]
					^((0-((m[4]>>30)&1))&7514112) //7514112=[!11,13,15,17,20,21,22!]
					^((0-((m[4]>>25)&1))&2676736) //2676736=[!11,12,14,15,19,21!]
					^((0-(m[4]&(1<<2)))&12627968) //12627968=[!12,13,15,22,23!]
					^((0-(m[4]&(1<<0)))&4493312) //4493312=[!12,15,18,22!]
					^((0-(m[4]&(1<<18)))&7602176) //7602176=[!18,20,21,22!]
					^((0-((m[4]>>23)&1))&165888) //165888=[!11,15,17!]
					^((0-(m[4]&(1<<20)))&5242880) //5242880=[!20,22!]
					^((0-((m[4]>>22)&1))&10240) //10240=[!11,13!]
					^(rotate_left(m[4],31)&2173368322) //2173368322=[!1,11,12,13,14,15,17,19,23,24,31!], 51769349=[!0,2,12,13,14,15,16,18,20,24,25!]
					^(rotate_left(m[4],30)&14544896) //14544896=[!12,13,14,15,16,18,19,20,22,23!], 58179584=[!14,15,16,17,18,20,21,22,24,25!]
					^(rotate_left(m[4],27)&520192) //520192=[!12,13,14,15,16,17,18!], 16646144=[!17,18,19,20,21,22,23!]
					^(rotate_left(m[4],29)&2148702208) //2148702208=[!11,12,15,17,20,31!], 9748484=[!2,14,15,18,20,23!]
					^(rotate_left(m[4],25)&112640) //112640=[!11,12,13,15,16!], 14417920=[!18,19,20,22,23!]
					^(rotate_left(m[4],28)&798720) //798720=[!12,13,18,19!], 12779520=[!16,17,22,23!]
					^(rotate_left(m[4],1)&5308416) //5308416=[!16,20,22!], 2654208=[!15,19,21!]
					^(rotate_left(m[4],3)&4194304) //4194304=[!22!], 524288=[!19!]
					;
			metset1precomp[5][15] = metset1precomp[4][15] ^ 0
					^((0-((m[4]>>21)&1))&1084153856) //1084153856=[!13,14,15,17,18,19,20,23,30!]
					^((0-((m[4]>>25)&1))&1077698564) //1077698564=[!2,13,14,18,19,20,21,30!]
					^((0-((m[4]>>30)&1))&26976256) //26976256=[!13,15,16,17,19,20,23,24!]
					^((0-((m[4]>>18)&1))&27860996) //27860996=[!2,13,16,19,21,23,24!]
					^((0-((m[4]>>23)&1))&19292164) //19292164=[!2,13,14,17,18,21,24!]
					^((0-((m[4]>>20)&1))&1082998784) //1082998784=[!14,16,18,19,23,30!]
					^((0-((m[4]>>31)&1))&26034176) //26034176=[!14,16,18,19,23,24!]
					^((0-(m[4]&(1<<2)))&1236992) //1236992=[!13,14,15,17,20!]
					^((0-((m[4]>>19)&1))&8699908) //8699908=[!2,14,15,18,23!]
					^((0-((m[4]>>24)&1))&3547136) //3547136=[!13,17,18,20,21!]
					^((0-(m[4]&(1<<0)))&2629636) //2629636=[!2,13,19,21!]
					^((0-((m[4]>>22)&1))&17080320) //17080320=[!13,15,18,24!]
					^((0-((m[4]>>15)&1))&2105344) //2105344=[!13,21!]
					^(rotate_left(m[4],0)&3278102533) //3278102533=[!0,2,13,14,15,16,17,21,22,24,25,30,31!], 3278102533=[!0,2,13,14,15,16,17,21,22,24,25,30,31!]
					^(rotate_left(m[4],4)&2097152) //2097152=[!21!], 131072=[!17!]
					;
		}
		Qtp1valsvecptr[t] = Qtp1valsptr;
		if (step_6()) step6ok = true;
		} while (cur != 0);
		if (!step6ok) return step5ok;
	}
	return step5ok;
}
bool step_4()
{
	static bool firsttime = true; if (firsttime) { cout << "t4 " << flush; firsttime = false; }
	const unsigned t = 4;
	UPDATE(t);
	bool step4ok = false;
	Qr30[offset+t-2] = rotate_left(Q[offset+t-2],30);
	const uint32 mpartial2 = 0 - sha1_f1(Q[offset+t-1], Qr30[offset+t-2], Qr30[offset+t-3]) - sha1_ac[0] - Qr30[offset+t-4];
	const uint32 metmask = 1006635034;
	for (uint32* Qtvalsptr = Qtp1valsvecptr[t-1]-1; Qtvalsptr >= Qtp1valsvec[t-1]; --Qtvalsptr) {
		Q[offset+t] = *Qtvalsptr;
		m[t-1] = *Qtvalsptr + metpartialvec[t-1];
		const uint32 metset1 = metset1precomp[3][4] ^ 0
				^(rotate_left(m[3],5)&2048) //2048=[!11!], 64=[!6!]
				;
		const uint32 Qtp1val = Qvalue[offset+t+1] ^ (Qprev[offset+t+1]&Q[offset+t]) ^ ((~metset1) & 939526144) ^ (xrng64()&2214589472);
		const uint32 mpartial = mpartial2 - rotate_left(Q[offset+t],5);
		metpartialvec[t] = mpartial;
		//uint32* Qtp1valsptr = Qtp1valsvec[t];
		bool didmp = false;
		uint32 cur = 0; const uint32 curmask = 65011712; // 5 bits
		do { cur -= 1; cur &= curmask;
		uint32* Qtp1valsptr = Qtp1valsvec[t];
		uint32 Qtp1cur = 0;
		do {
			Q[offset+t+1] = Qtp1cur ^ cur ^ Qtp1val;
			Qtp1cur -= 1; Qtp1cur &= 2214589472^curmask; // 17 bits of freedom
			m[t] = Q[offset+t+1] + mpartial;
			if (0 != ((m[t]^metset1)&67108890)) break;
			uint32 metxorfix = (m[t]^metset1) & 939526144;
			*(Qtp1valsptr++) = Q[offset+t+1]^metxorfix;
		} while (Qtp1cur != 0);
		//} while (cur != 0);
		if (Qtp1valsptr == Qtp1valsvec[t]) continue;
		step4ok = true;
		if (!didmp) {
			metset1precomp[4][5] = metset1precomp[3][5] ^ 0;
			metset1precomp[4][6] = metset1precomp[3][6] ^ 0;
			metset1precomp[4][7] = metset1precomp[3][7] ^ 0
					^(rotate_left(m[3],0)&8) //8=[!3!], 8=[!3!]
					;
			metset1precomp[4][8] = metset1precomp[3][8] ^ 0;
			metset1precomp[4][9] = metset1precomp[3][9] ^ 0
					^(rotate_left(m[3],0)&8) //8=[!3!], 8=[!3!]
					;
			metset1precomp[4][10] = metset1precomp[3][10] ^ 0;
			metset1precomp[4][11] = metset1precomp[3][11] ^ 0
					^(rotate_left(m[3],0)&8) //8=[!3!], 8=[!3!]
					;
			metset1precomp[4][12] = metset1precomp[3][12] ^ 0;
			metset1precomp[4][13] = metset1precomp[3][13] ^ 0
					^((0-((m[3]>>24)&1))&29229056) //29229056=[!17,18,19,20,21,23,24!]
					^((0-(m[3]&(1<<15)))&20840448) //20840448=[!17,18,19,20,21,24!]
					^((0-(m[3]&(1<<1)))&4063232) //4063232=[!17,18,19,20,21!]
					^((0-((m[3]>>22)&1))&17694720) //17694720=[!17,18,19,24!]
					^((0-(m[3]&(1<<0)))&19922944) //19922944=[!20,21,24!]
					^((0-(m[3]&(1<<3)))&1441792) //1441792=[!17,18,20!]
					^((0-(m[3]&(1<<12)))&17432576) //17432576=[!17,19,24!]
					^((0-(m[3]&(1<<16)))&3407872) //3407872=[!18,20,21!]
					^((0-((m[3]>>23)&1))&1441792) //1441792=[!17,18,20!]
					^((0-(m[3]&(1<<6)))&17301504) //17301504=[!19,24!]
					^((0-(m[3]&(1<<17)))&17301504) //17301504=[!19,24!]
					^((0-((m[3]>>21)&1))&2359296) //2359296=[!18,21!]
					^((0-((m[3]>>25)&1))&1572864) //1572864=[!19,20!]
					^(rotate_left(m[3],30)&2164129794) //2164129794=[!1,17,18,19,20,21,22,23,31!], 66584586=[!1,3,19,20,21,22,23,24,25!]
					^(rotate_left(m[3],1)&19791872) //19791872=[!17,18,19,21,24!], 9895936=[!16,17,18,20,23!]
					^(rotate_left(m[3],31)&2169241600) //2169241600=[!18,19,22,24,31!], 43515905=[!0,19,20,23,25!]
					^(rotate_left(m[3],3)&3276800) //3276800=[!17,20,21!], 409600=[!14,17,18!]
					^(rotate_left(m[3],6)&16777216) //16777216=[!24!], 262144=[!18!]
					^(rotate_left(m[3],22)&1048576) //1048576=[!20!], 1073741824=[!30!]
					;
			metset1precomp[4][14] = metset1precomp[3][14] ^ 0
					^((0-(m[3]&(1<<1)))&3227236354) //3227236354=[!1,11,12,13,15,16,17,19,20,22,30,31!]
					^((0-((m[3]>>23)&1))&14637056) //14637056=[!11,12,14,16,17,18,19,20,22,23!]
					^((0-((m[3]>>15)&1))&5728256) //5728256=[!11,13,14,16,17,18,20,22!]
					^((0-((m[3]>>17)&1))&5371904) //5371904=[!11,12,13,14,15,16,20,22!]
					^((0-(m[3]&(1<<0)))&3226050560) //3226050560=[!13,15,16,19,22,30,31!]
					^((0-((m[3]>>16)&1))&7659520) //7659520=[!13,14,15,18,20,21,22!]
					^((0-((m[3]>>21)&1))&5689344) //5689344=[!12,14,15,17,18,20,22!]
					^((0-(m[3]&(1<<3)))&7520256) //7520256=[!14,15,17,20,21,22!]
					^((0-((m[3]>>24)&1))&4067328) //4067328=[!12,17,18,19,20,21!]
					^((0-((m[3]>>25)&1))&4689920) //4689920=[!12,15,16,17,18,22!]
					^((0-((m[3]>>20)&1))&309248) //309248=[!11,12,13,15,18!]
					^((0-((m[3]>>30)&1))&4409344) //4409344=[!11,14,16,17,22!]
					^((0-((m[3]>>18)&1))&2248704) //2248704=[!12,14,17,21!]
					^((0-(m[3]&(1<<6)))&2230272) //2230272=[!11,17,21!]
					^((0-(m[3]&(1<<12)))&2293760) //2293760=[!16,17,21!]
					^((0-((m[3]>>14)&1))&71680) //71680=[!11,12,16!]
					^((0-((m[3]>>19)&1))&53248) //53248=[!12,14,15!]
					^((0-((m[3]>>22)&1))&2121728) //2121728=[!13,14,21!]
					^(rotate_left(m[3],0)&56123393) //56123393=[!0,13,14,19,20,22,24,25!], 56123393=[!0,13,14,19,20,22,24,25!]
					^(rotate_left(m[3],1)&2048) //2048=[!11!], 1024=[!10!]
					^(rotate_left(m[3],30)&2048) //2048=[!11!], 8192=[!13!]
					;
			metset1precomp[4][15] = metset1precomp[3][15] ^ 0
					^((0-(m[3]&(1<<1)))&1104470020) //1104470020=[!2,13,14,15,18,20,22,23,24,30!]
					^((0-(m[3]&(1<<3)))&27238400) //27238400=[!13,15,16,17,18,19,20,23,24!]
					^((0-((m[3]>>22)&1))&1092444164) //1092444164=[!2,13,14,16,18,19,20,24,30!]
					^((0-((m[3]>>25)&1))&32325636) //32325636=[!2,14,16,18,19,21,22,23,24!]
					^((0-((m[3]>>16)&1))&26042372) //26042372=[!2,13,14,16,18,19,23,24!]
					^((0-((m[3]>>30)&1))&1075781636) //1075781636=[!2,13,16,17,18,19,20,30!]
					^((0-(m[3]&(1<<0)))&1096065024) //1096065024=[!13,15,18,20,22,24,30!]
					^((0-((m[3]>>18)&1))&1091674116) //1091674116=[!2,13,15,16,20,24,30!]
					^((0-((m[3]>>21)&1))&25903108) //25903108=[!2,14,16,17,19,23,24!]
					^((0-((m[3]>>15)&1))&11288580) //11288580=[!2,14,18,19,21,23!]
					^((0-((m[3]>>17)&1))&1083981824) //1083981824=[!14,18,19,20,23,30!]
					^((0-((m[3]>>20)&1))&1075003396) //1075003396=[!2,14,16,17,20,30!]
					^((0-((m[3]>>24)&1))&1090600964) //1090600964=[!2,14,16,24,30!]
					^((0-((m[3]>>23)&1))&1082400768) //1082400768=[!13,18,23,30!]
					^((0-(m[3]&(1<<6)))&18939904) //18939904=[!16,21,24!]
					^((0-(m[3]&(1<<12)))&16850944) //16850944=[!13,16,24!]
					^((0-((m[3]>>14)&1))&2105344) //2105344=[!13,21!]
					^((0-((m[3]>>19)&1))&98304) //98304=[!15,16!]
					;
			didmp = true;
		}
		Qtp1valsvecptr[t] = Qtp1valsptr;
		step_5();
		} while (cur != 0);
	}
	return step4ok;
}
bool step_3()
{
	static bool firsttime = true; if (firsttime) { cout << "t3 " << flush; firsttime = false; }
	const unsigned t = 3;
	UPDATE(t);
	bool step3ok = false;
	Qr30[offset+t-2] = rotate_left(Q[offset+t-2],30);
	const uint32 mpartial2 = 0 - sha1_f1(Q[offset+t-1], Qr30[offset+t-2], Qr30[offset+t-3]) - sha1_ac[0] - Qr30[offset+t-4];
	const uint32 metmask = 1006632964;
	for (uint32* Qtvalsptr = Qtp1valsvecptr[t-1]-1; Qtvalsptr >= Qtp1valsvec[t-1]; --Qtvalsptr) {
		Q[offset+t] = *Qtvalsptr;
		m[t-1] = *Qtvalsptr + metpartialvec[t-1];
		const uint32 metset1 = metset1precomp[2][3] ^ 0
				;
		const uint32 Qtp1val = Qvalue[offset+t+1] ^ (Qprev[offset+t+1]&Q[offset+t]) ^ ((~metset1) & 939524100) ^ (xrng64()&2181038096);
		const uint32 mpartial = mpartial2 - rotate_left(Q[offset+t],5);
		metpartialvec[t] = mpartial;
		uint32* Qtp1valsptr = Qtp1valsvec[t];
		uint32 cur = 0; const uint32 curmask = 33554432;
		do { cur -= 1; cur &= curmask;
		uint32 Qtp1cur = 0;
		do {
			Q[offset+t+1] = Qtp1cur ^ cur ^ Qtp1val;
			Qtp1cur -= 1; Qtp1cur &= 2181038096^curmask; // 3 bits of freedom
			m[t] = Q[offset+t+1] + mpartial;
			if (0 != ((m[t]^metset1)&67108864)) break;
			uint32 metxorfix = (m[t]^metset1) & 939524100;
			*(Qtp1valsptr++) = Q[offset+t+1]^metxorfix;
		} while (Qtp1cur != 0);
		} while (cur != 0);
		if (Qtp1valsptr == Qtp1valsvec[t]) continue;
		step3ok = true;
		metset1precomp[3][4] = metset1precomp[2][4] ^ 0
				^(rotate_left(m[2],0)&2048) //2048=[!11!], 2048=[!11!]
				;
		metset1precomp[3][5] = metset1precomp[2][5] ^ 0
				;
		metset1precomp[3][6] = metset1precomp[2][6] ^ 0
				;
		metset1precomp[3][7] = metset1precomp[2][7] ^ 0
				;
		metset1precomp[3][8] = metset1precomp[2][8] ^ 0
				;
		metset1precomp[3][9] = metset1precomp[2][9] ^ 0
				;
		metset1precomp[3][10] = metset1precomp[2][10] ^ 0
				;
		metset1precomp[3][11] = metset1precomp[2][11] ^ 0
				;
		metset1precomp[3][12] = metset1precomp[2][12] ^ 0
				^(rotate_left(m[2],31)&2147483648) //2147483648=[!31!], 1=[!0!]
				;
		metset1precomp[3][13] = metset1precomp[2][13] ^ 0
				^((0-(m[2]&(1<<16)))&18612224) //18612224=[!18,19,20,24!]
				^((0-((m[2]>>23)&1))&3932160) //3932160=[!18,19,20,21!]
				^((0-((m[2]>>24)&1))&1966080) //1966080=[!17,18,19,20!]
				^((0-((m[2]>>31)&1))&3538944) //3538944=[!17,18,20,21!]
				^((0-(m[2]&(1<<0)))&3670016) //3670016=[!19,20,21!]
				^((0-(m[2]&(1<<11)))&17432576) //17432576=[!17,19,24!]
				^((0-(m[2]&(1<<14)))&3407872) //3407872=[!18,20,21!]
				^((0-(m[2]&(1<<15)))&17432576) //17432576=[!17,19,24!]
				^((0-((m[2]>>18)&1))&3276800) //3276800=[!17,20,21!]
				^((0-((m[2]>>30)&1))&917504) //917504=[!17,18,19!]
				^(rotate_left(m[2],0)&2197291010) //2197291010=[!1,19,20,21,22,23,25,31!], 2197291010=[!1,19,20,21,22,23,25,31!]
				^(rotate_left(m[2],1)&2097152) //2097152=[!21!], 1048576=[!20!]
				^(rotate_left(m[2],5)&131072) //131072=[!17!], 4096=[!12!]
				^(rotate_left(m[2],26)&524288) //524288=[!19!], 33554432=[!25!]
				^(rotate_left(m[2],30)&1048576) //1048576=[!20!], 4194304=[!22!]
				;
		metset1precomp[3][14] = metset1precomp[2][14] ^ 0
				^((0-((m[2]>>30)&1))&3223296000) //3223296000=[!11,12,15,16,17,18,19,20,30,31!]
				^((0-((m[2]>>14)&1))&7661568) //7661568=[!11,13,14,15,18,20,21,22!]
				^((0-((m[2]>>23)&1))&5568512) //5568512=[!11,12,13,14,15,18,20,22!]
				^((0-((m[2]>>18)&1))&7659520) //7659520=[!13,14,15,18,20,21,22!]
				^((0-((m[2]>>31)&1))&7641088) //7641088=[!11,12,15,18,20,21,22!]
				^((0-(m[2]&(1<<0)))&6959104) //6959104=[!12,13,17,19,21,22!]
				^((0-((m[2]>>16)&1))&5476352) //5476352=[!12,15,16,17,20,22!]
				^((0-((m[2]>>22)&1))&6379520) //6379520=[!11,12,14,16,21,22!]
				^((0-((m[2]>>24)&1))&2177024) //2177024=[!11,12,13,16,21!]
				^((0-(m[2]&(1<<11)))&2297856) //2297856=[!12,16,17,21!]
				^((0-((m[2]>>15)&1))&2295808) //2295808=[!11,16,17,21!]
				^((0-(m[2]&(1<<1)))&77824) //77824=[!12,13,16!]
				^((0-((m[2]>>12)&1))&71680) //71680=[!11,12,16!]
				^((0-((m[2]>>17)&1))&71680) //71680=[!11,12,16!]
				^((0-((m[2]>>21)&1))&83968) //83968=[!11,14,16!]
				^((0-((m[2]>>25)&1))&86016) //86016=[!12,14,16!]
				^((0-((m[2]>>20)&1))&67584) //67584=[!11,16!]
				^(rotate_left(m[2],30)&1087021056) //1087021056=[!13,15,17,19,22,23,30!], 53116929=[!0,15,17,19,21,24,25!]
				^(rotate_left(m[2],2)&2048) //2048=[!11!], 512=[!9!]
				;
		metset1precomp[3][15] = metset1precomp[2][15] ^ 0
				^((0-((m[2]>>30)&1))&33357828) //33357828=[!2,16,18,19,20,21,22,23,24!]
				^((0-((m[2]>>23)&1))&17784836) //17784836=[!2,13,14,16,17,18,19,24!]
				^((0-((m[2]>>14)&1))&28114948) //28114948=[!2,16,18,19,21,23,24!]
				^((0-((m[2]>>18)&1))&25772036) //25772036=[!2,14,16,19,23,24!]
				^((0-((m[2]>>22)&1))&1100226560) //1100226560=[!13,18,20,23,24,30!]
				^((0-((m[2]>>31)&1))&25772036) //25772036=[!2,14,16,19,23,24!]
				^((0-(m[2]&(1<<0)))&5521412) //5521412=[!2,14,18,20,22!]
				^((0-(m[2]&(1<<16)))&1083965440) //1083965440=[!18,19,20,23,30!]
				^((0-((m[2]>>25)&1))&1075347460) //1075347460=[!2,15,19,20,30!]
				^((0-(m[2]&(1<<11)))&16850944) //16850944=[!13,16,24!]
				^((0-((m[2]>>15)&1))&16850944) //16850944=[!13,16,24!]
				^((0-(m[2]&(1<<12)))&2105344) //2105344=[!13,21!]
				^((0-((m[2]>>17)&1))&2105344) //2105344=[!13,21!]
				^((0-((m[2]>>20)&1))&1073741828) //1073741828=[!2,30!]
				^(rotate_left(m[2],31)&3252666369) //3252666369=[!0,14,15,16,17,18,19,20,22,23,24,30,31!], 2210365443=[!0,1,15,16,17,18,19,20,21,23,24,25,31!]
				^(rotate_left(m[2],0)&2185994243) //2185994243=[!0,1,13,15,16,17,19,22,25,31!], 2185994243=[!0,1,13,15,16,17,19,22,25,31!]
				^(rotate_left(m[2],29)&1081589760) //1081589760=[!14,15,16,17,18,20,21,22,30!], 62783490=[!1,17,18,19,20,21,23,24,25!]
				^(rotate_left(m[2],26)&303104) //303104=[!13,15,18!], 19398656=[!19,21,24!]
				^(rotate_left(m[2],24)&73728) //73728=[!13,16!], 18874368=[!21,24!]
				^(rotate_left(m[2],20)&2097152) //2097152=[!21!], 2=[!1!]
				^(rotate_left(m[2],22)&16384) //16384=[!14!], 16777216=[!24!]
				;
		Qtp1valsvecptr[t] = Qtp1valsptr;
		step_4();
	}
	return step3ok;
}
bool step_2()
{
	static bool firsttime = true; if (firsttime) { cout << "t2 " << flush; firsttime = false; }
	const unsigned t = 2;
	UPDATE(t);
	bool step2ok = false;
	Qr30[offset+t-2] = rotate_left(Q[offset+t-2],30);
	const uint32 mpartial2 = 0 - sha1_f1(Q[offset+t-1], Qr30[offset+t-2], Qr30[offset+t-3]) - sha1_ac[0] - Qr30[offset+t-4];
	const uint32 metmask = 1006632988;
	for (uint32* Qtvalsptr = Qtp1valsvecptr[t-1]-1; Qtvalsptr >= Qtp1valsvec[t-1]; --Qtvalsptr) {
		Q[offset+t] = *Qtvalsptr;
		m[t-1] = *Qtvalsptr + metpartialvec[t-1];
		const uint32 metset1 = metset1precomp[1][2] ^ 0
				;
		const uint32 Qtp1val = Qvalue[offset+t+1] ^ (Qprev[offset+t+1]&Q[offset+t]) ^ ((~metset1) & 671088640) ^ (xrng64()&2181038080);
		const uint32 mpartial = mpartial2 - rotate_left(Q[offset+t],5);
		metpartialvec[t] = mpartial;
		uint32* Qtp1valsptr = Qtp1valsvec[t];
		uint32 cur = 0; const uint32 curmask = 33554432;
		do { cur -= 1; cur &= curmask;
		uint32 Qtp1cur = 0;
		do {
			Q[offset+t+1] = Qtp1cur ^ cur ^ Qtp1val;
			Qtp1cur -= 1; Qtp1cur &= 2181038080^curmask; // 2 bits of freedom
			m[t] = Q[offset+t+1] + mpartial;
			if (0 != ((m[t]^metset1)&335544348)) break;
			uint32 metxorfix = (m[t]^metset1) & 671088640;
			*(Qtp1valsptr++) = Q[offset+t+1]^metxorfix;
		} while (Qtp1cur != 0);
		} while (cur != 0);
		if (Qtp1valsptr == Qtp1valsvec[t]) continue;
		step2ok = true;
		metset1precomp[2][3] = metset1precomp[1][3] ^ 0
				;
		metset1precomp[2][4] = metset1precomp[1][4] ^ 0
				^(rotate_left(m[1],5)&2048) //2048=[!11!], 64=[!6!]
				;
		metset1precomp[2][5] = metset1precomp[1][5] ^ 0
				;
		metset1precomp[2][6] = metset1precomp[1][6] ^ 0
				;
		metset1precomp[2][7] = metset1precomp[1][7] ^ 0
				^(rotate_left(m[1],0)&8) //8=[!3!], 8=[!3!]
				;
		metset1precomp[2][8] = metset1precomp[1][8] ^ 0
				;
		metset1precomp[2][9] = metset1precomp[1][9] ^ 0
				^(rotate_left(m[1],0)&268435468) //268435468=[!2,3,28!], 268435468=[!2,3,28!]
				;
		metset1precomp[2][10] = metset1precomp[1][10] ^ 0
				;
		metset1precomp[2][11] = metset1precomp[1][11] ^ 0
				;
		metset1precomp[2][12] = metset1precomp[1][12] ^ 0
				^(rotate_left(m[1],31)&2147483648) //2147483648=[!31!], 1=[!0!]
				;
		metset1precomp[2][13] = metset1precomp[1][13] ^ 0
				^((0-((m[1]>>26)&1))&25034752) //25034752=[!17,18,19,20,21,22,24!]
				^((0-(m[1]&(1<<1)))&2151546880) //2151546880=[!17,18,19,20,21,31!]
				^((0-((m[1]>>28)&1))&20840448) //20840448=[!17,18,19,20,21,24!]
				^((0-((m[1]>>21)&1))&20316160) //20316160=[!17,18,20,21,24!]
				^((0-((m[1]>>22)&1))&18743296) //18743296=[!17,18,19,20,24!]
				^((0-((m[1]>>23)&1))&4063232) //4063232=[!17,18,19,20,21!]
				^((0-(m[1]&(1<<2)))&17694720) //17694720=[!17,18,19,24!]
				^((0-(m[1]&(1<<3)))&3538944) //3538944=[!17,18,20,21!]
				^((0-(m[1]&(1<<16)))&3538944) //3538944=[!17,18,20,21!]
				^((0-((m[1]>>20)&1))&18481152) //18481152=[!17,19,20,24!]
				^((0-((m[1]>>24)&1))&22544384) //22544384=[!19,20,22,24!]
				^((0-((m[1]>>25)&1))&26738688) //26738688=[!19,20,23,24!]
				^((0-(m[1]&(1<<13)))&17432576) //17432576=[!17,19,24!]
				^((0-(m[1]&(1<<18)))&19398656) //19398656=[!19,21,24!]
				^((0-((m[1]>>29)&1))&1441792) //1441792=[!17,18,20!]
				^((0-(m[1]&(1<<0)))&17825792) //17825792=[!20,24!]
				^((0-(m[1]&(1<<6)))&17301504) //17301504=[!19,24!]
				^(rotate_left(m[1],2)&131072) //131072=[!17!], 32768=[!15!]
				^(rotate_left(m[1],3)&131072) //131072=[!17!], 16384=[!14!]
				;
		metset1precomp[2][14] = metset1precomp[1][14] ^ 0
				^((0-((m[1]>>21)&1))&5490688) //5490688=[!11,14,15,16,17,20,22!]
				^((0-(m[1]&(1<<3)))&1349632) //1349632=[!11,12,15,18,20!]
				^((0-(m[1]&(1<<2)))&4366336) //4366336=[!13,15,17,22!]
				^((0-(m[1]&(1<<6)))&2230272) //2230272=[!11,17,21!]
				^((0-(m[1]&(1<<13)))&2293760) //2293760=[!16,17,21!]
				^((0-(m[1]&(1<<16)))&7340032) //7340032=[!20,21,22!]
				^((0-(m[1]&(1<<0)))&163840) //163840=[!15,17!]
				^(rotate_left(m[1],0)&669704195) //669704195=[!0,1,13,14,15,17,19,21,22,23,24,25,26,29!], 669704195=[!0,1,13,14,15,17,19,21,22,23,24,25,26,29!]
				^(rotate_left(m[1],29)&1081554944) //1081554944=[!11,12,13,16,17,18,20,21,22,30!], 62504962=[!1,14,15,16,19,20,21,23,24,25!]
				^(rotate_left(m[1],24)&3647488) //3647488=[!11,13,15,16,17,18,20,21!], 933756928=[!19,21,23,24,25,26,28,29!]
				^(rotate_left(m[1],18)&3954688) //3954688=[!11,12,14,18,19,20,21!], 369098767=[!0,1,2,3,25,26,28!]
				^(rotate_left(m[1],19)&5847040) //5847040=[!11,12,13,16,19,20,22!], 654311435=[!0,1,3,24,25,26,29!]
				^(rotate_left(m[1],30)&3223410688) //3223410688=[!11,12,14,16,21,30,31!], 8740867=[!0,1,13,14,16,18,23!]
				^(rotate_left(m[1],21)&12728320) //12728320=[!11,12,13,17,22,23!], 297795590=[!1,2,22,23,24,28!]
				^(rotate_left(m[1],23)&1288192) //1288192=[!11,13,15,16,17,20!], 659554304=[!20,22,24,25,26,29!]
				^(rotate_left(m[1],25)&6686720) //6686720=[!11,17,18,21,22!], 855900160=[!18,24,25,28,29!]
				^(rotate_left(m[1],31)&6459392) //6459392=[!12,15,17,21,22!], 12918784=[!13,16,18,22,23!]
				^(rotate_left(m[1],2)&2152005632) //2152005632=[!16,18,22,31!], 538001408=[!14,16,20,29!]
				^(rotate_left(m[1],22)&4554752) //4554752=[!15,16,18,22!], 369098753=[!0,25,26,28!]
				^(rotate_left(m[1],26)&5324800) //5324800=[!14,16,20,22!], 340787200=[!20,22,26,28!]
				^(rotate_left(m[1],14)&51200) //51200=[!11,14,15!], 536870915=[!0,1,29!]
				^(rotate_left(m[1],16)&143360) //143360=[!12,13,17!], 805306370=[!1,28,29!]
				^(rotate_left(m[1],27)&802816) //802816=[!14,18,19!], 25690112=[!19,23,24!]
				^(rotate_left(m[1],20)&133120) //133120=[!11,17!], 545259520=[!23,29!]
				^(rotate_left(m[1],28)&4196352) //4196352=[!11,22!], 67141632=[!15,26!]
				^(rotate_left(m[1],1)&65536) //65536=[!16!], 32768=[!15!]
				^(rotate_left(m[1],3)&2097152) //2097152=[!21!], 262144=[!18!]
				^(rotate_left(m[1],10)&2048) //2048=[!11!], 2=[!1!]
				;
		metset1precomp[2][15] = metset1precomp[1][15] ^ 0
				^((0-(m[1]&(1<<1)))&1106567172) //1106567172=[!2,13,14,15,18,20,21,22,23,24,30!]
				^((0-((m[1]>>29)&1))&1102733312) //1102733312=[!13,14,17,19,20,21,23,24,30!]
				^((0-(m[1]&(1<<3)))&1099513856) //1099513856=[!14,16,19,23,24,30!]
				^((0-((m[1]>>20)&1))&1085808640) //1085808640=[!13,19,20,21,23,30!]
				^((0-((m[1]>>23)&1))&1099218944) //1099218944=[!14,15,18,23,24,30!]
				^((0-((m[1]>>25)&1))&745476) //745476=[!2,13,14,16,17,19!]
				^((0-(m[1]&(1<<0)))&21127168) //21127168=[!13,14,17,22,24!]
				^((0-(m[1]&(1<<2)))&11698176) //11698176=[!15,17,20,21,23!]
				^((0-((m[1]>>16)&1))&25755652) //25755652=[!2,16,19,23,24!]
				^((0-((m[1]>>18)&1))&1092616196) //1092616196=[!2,21,24,30!]
				^((0-((m[1]>>24)&1))&16949248) //16949248=[!13,15,17,24!]
				^((0-((m[1]>>26)&1))&212996) //212996=[!2,14,16,17!]
				^((0-((m[1]>>28)&1))&8953856) //8953856=[!13,15,19,23!]
				^((0-(m[1]&(1<<6)))&18939904) //18939904=[!16,21,24!]
				^((0-(m[1]&(1<<13)))&16850944) //16850944=[!13,16,24!]
				^((0-((m[1]>>22)&1))&114688) //114688=[!14,15,16!]
				^((0-((m[1]>>14)&1))&2105344) //2105344=[!13,21!]
				^(rotate_left(m[1],28)&1081581568) //1081581568=[!13,15,16,17,18,20,21,22,30!], 125435908=[!2,17,19,20,21,22,24,25,26!]
				^(rotate_left(m[1],29)&7069696) //7069696=[!13,14,15,16,17,19,21,22!], 56557568=[!16,17,18,19,20,22,24,25!]
				^(rotate_left(m[1],30)&26042368) //26042368=[!13,14,16,18,19,23,24!], 104169472=[!15,16,18,20,21,25,26!]
				^(rotate_left(m[1],2)&1102315520) //1102315520=[!18,20,21,23,24,30!], 275578880=[!16,18,19,21,22,28!]
				^(rotate_left(m[1],6)&2097152) //2097152=[!21!], 32768=[!15!]
				^(rotate_left(m[1],13)&4) //4=[!2!], 2097152=[!21!]
				^(rotate_left(m[1],26)&8192) //8192=[!13!], 524288=[!19!]
				;
		Qtp1valsvecptr[t] = Qtp1valsptr;
		step_3();
	}
	return step2ok;
}
bool step_1()
{
	static bool firsttime = true; if (firsttime) { cout << "t1 " << flush; firsttime = false; }
	const unsigned t = 1;
	UPDATE(t);
	bool step1ok = false;
	Qr30[offset+t-2] = rotate_left(Q[offset+t-2],30);
	const uint32 mpartial2 = 0 - sha1_f1(Q[offset+t-1], Qr30[offset+t-2], Qr30[offset+t-3]) - sha1_ac[0] - Qr30[offset+t-4];
	const uint32 metmask = 1207963664;
	for (uint32* Qtvalsptr = Qtp1valsvecptr[t-1]-1; Qtvalsptr >= Qtp1valsvec[t-1]; --Qtvalsptr) {
		Q[offset+t] = *Qtvalsptr;
		m[t-1] = *Qtvalsptr + metpartialvec[t-1];
		const uint32 metset1 = metset1precomp[0][1] ^ 0
				;
		const uint32 Qtp1val = Qvalue[offset+t+1] ^ (Qprev[offset+t+1]&Q[offset+t]) ^ ((~metset1) & 134217728) ^ (xrng64()&805306372);
		const uint32 mpartial = mpartial2 - rotate_left(Q[offset+t],5);
		metpartialvec[t] = mpartial;
		uint32* Qtp1valsptr = Qtp1valsvec[t];
		uint32 cur = 0; const uint32 curmask = 805306372;
		do { cur -= 1; cur &= curmask;
		uint32 Qtp1cur = 0;
		do {
			Q[offset+t+1] = Qtp1cur ^ cur ^ Qtp1val;
			Qtp1cur -= 1; Qtp1cur &= 805306372^curmask; // 3 bits of freedom
			m[t] = Q[offset+t+1] + mpartial;
			if (0 != ((m[t]^metset1)&1073745936)) break;
			uint32 metxorfix = (m[t]^metset1) & 134217728;
			*(Qtp1valsptr++) = Q[offset+t+1]^metxorfix;
		} while (Qtp1cur != 0);
		} while (cur != 0);
		if (Qtp1valsptr == Qtp1valsvec[t]) continue;
		step1ok = true;
		metset1precomp[1][2] = metset1precomp[0][2] ^ 0
				;
		metset1precomp[1][3] = metset1precomp[0][3] ^ 0
				;
		metset1precomp[1][4] = metset1precomp[0][4] ^ 0
				;
		metset1precomp[1][5] = metset1precomp[0][5] ^ 0
				;
		metset1precomp[1][6] = metset1precomp[0][6] ^ 0
				;
		metset1precomp[1][7] = metset1precomp[0][7] ^ 0
				;
		metset1precomp[1][8] = metset1precomp[0][8] ^ 0
				;
		metset1precomp[1][9] = metset1precomp[0][9] ^ 0
				;
		metset1precomp[1][10] = metset1precomp[0][10] ^ 0
				;
		metset1precomp[1][11] = metset1precomp[0][11] ^ 0
				;
		metset1precomp[1][12] = metset1precomp[0][12] ^ 0
				^(rotate_left(m[0],1)&2147483648) //2147483648=[!31!], 1073741824=[!30!]
				;
		metset1precomp[1][13] = metset1precomp[0][13] ^ 0
				^((0-(m[0]&(1<<2)))&3538944) //3538944=[!17,18,20,21!]
				^((0-(m[0]&(1<<16)))&18612224) //18612224=[!18,19,20,24!]
				^((0-((m[0]>>31)&1))&19660800) //19660800=[!18,19,21,24!]
				^((0-(m[0]&(1<<3)))&1441792) //1441792=[!17,18,20!]
				^((0-(m[0]&(1<<11)))&17432576) //17432576=[!17,19,24!]
				^((0-(m[0]&(1<<14)))&3407872) //3407872=[!18,20,21!]
				^((0-(m[0]&(1<<19)))&19922944) //19922944=[!20,21,24!]
				^((0-(m[0]&(1<<0)))&16908288) //16908288=[!17,24!]
				^((0-(m[0]&(1<<20)))&18874368) //18874368=[!21,24!]
				^((0-((m[0]>>30)&1))&2228224) //2228224=[!17,21!]
				^(rotate_left(m[0],0)&2212888588) //2212888588=[!2,3,17,18,21,22,23,24,25,31!], 2212888588=[!2,3,17,18,21,22,23,24,25,31!]
				^(rotate_left(m[0],31)&4063232) //4063232=[!17,18,19,20,21!], 8126464=[!18,19,20,21,22!]
				^(rotate_left(m[0],29)&3932160) //3932160=[!18,19,20,21!], 31457280=[!21,22,23,24!]
				^(rotate_left(m[0],30)&2490370) //2490370=[!1,17,18,21!], 9961480=[!3,19,20,23!]
				^(rotate_left(m[0],26)&17563648) //17563648=[!18,19,24!], 1124073472=[!24,25,30!]
				^(rotate_left(m[0],27)&17432576) //17432576=[!17,19,24!], 557842432=[!22,24,29!]
				^(rotate_left(m[0],2)&16777216) //16777216=[!24!], 4194304=[!22!]
				^(rotate_left(m[0],5)&131072) //131072=[!17!], 4096=[!12!]
				^(rotate_left(m[0],22)&524288) //524288=[!19!], 536870912=[!29!]
				^(rotate_left(m[0],25)&262144) //262144=[!18!], 33554432=[!25!]
				^(rotate_left(m[0],28)&131072) //131072=[!17!], 2097152=[!21!]
				;
		metset1precomp[1][14] = metset1precomp[0][14] ^ 0
				^((0-((m[0]>>20)&1))&5765120) //5765120=[!11,12,13,14,15,16,17,18,20,22!]
				^((0-((m[0]>>14)&1))&7655424) //7655424=[!12,14,15,18,20,21,22!]
				^((0-((m[0]>>19)&1))&5466112) //5466112=[!11,13,14,16,17,20,22!]
				^((0-((m[0]>>21)&1))&6481920) //6481920=[!11,13,14,15,17,21,22!]
				^((0-((m[0]>>23)&1))&4009984) //4009984=[!12,13,16,18,19,20,21!]
				^((0-((m[0]>>25)&1))&5490688) //5490688=[!11,14,15,16,17,20,22!]
				^((0-(m[0]&(1<<2)))&5543936) //5543936=[!11,12,15,18,20,22!]
				^((0-((m[0]>>30)&1))&1074358272) //1074358272=[!11,13,14,16,19,30!]
				^((0-(m[0]&(1<<0)))&1074081792) //1074081792=[!12,13,16,18,30!]
				^((0-(m[0]&(1<<3)))&3325952) //3325952=[!14,15,17,20,21!]
				^((0-((m[0]>>16)&1))&5455872) //5455872=[!14,16,17,20,22!]
				^((0-((m[0]>>24)&1))&1355776) //1355776=[!12,13,15,18,20!]
				^((0-(m[0]&(1<<11)))&2297856) //2297856=[!12,16,17,21!]
				^((0-((m[0]>>22)&1))&215040) //215040=[!11,14,16,17!]
				^((0-((m[0]>>29)&1))&2265088) //2265088=[!12,15,17,21!]
				^((0-((m[0]>>31)&1))&1163264) //1163264=[!14,15,16,20!]
				^((0-((m[0]>>18)&1))&86016) //86016=[!12,14,16!]
				^((0-(m[0]&(1<<12)))&69632) //69632=[!12,16!]
				^((0-((m[0]>>17)&1))&10240) //10240=[!11,13!]
				^(rotate_left(m[0],19)&7280640) //7280640=[!11,12,16,17,18,19,21,22!], 3808428045=[!0,2,3,24,25,29,30,31!]
				^(rotate_left(m[0],31)&1081387008) //1081387008=[!11,13,15,18,20,21,22,30!], 2162774016=[!12,14,16,19,21,22,23,31!]
				^(rotate_left(m[0],2)&2048) //2048=[!11!], 512=[!9!]
				^(rotate_left(m[0],29)&4096) //4096=[!12!], 32768=[!15!]
				;
		metset1precomp[1][15] = metset1precomp[0][15] ^ 0
				^((0-(m[0]&(1<<3)))&27238400) //27238400=[!13,15,16,17,18,19,20,23,24!]
				^((0-((m[0]>>23)&1))&31244292) //31244292=[!2,14,15,18,19,20,22,23,24!]
				^((0-((m[0]>>24)&1))&1085497348) //1085497348=[!2,13,14,16,17,20,21,23,30!]
				^((0-(m[0]&(1<<0)))&2172420096) //2172420096=[!15,18,19,20,21,22,24,31!]
				^((0-((m[0]>>14)&1))&28131332) //28131332=[!2,14,16,18,19,21,23,24!]
				^((0-((m[0]>>25)&1))&1088110592) //1088110592=[!14,16,17,19,20,22,23,30!]
				^((0-((m[0]>>30)&1))&1097490432) //1097490432=[!13,14,17,19,21,22,24,30!]
				^((0-((m[0]>>21)&1))&1099522048) //1099522048=[!13,14,16,19,23,24,30!]
				^((0-((m[0]>>22)&1))&1092190212) //1092190212=[!2,15,16,19,20,24,30!]
				^((0-((m[0]>>31)&1))&12009472) //12009472=[!14,16,17,18,20,21,23!]
				^((0-(m[0]&(1<<2)))&1099513856) //1099513856=[!14,16,19,23,24,30!]
				^((0-((m[0]>>16)&1))&1083998208) //1083998208=[!15,18,19,20,23,30!]
				^((0-((m[0]>>19)&1))&11091972) //11091972=[!2,14,16,19,21,23!]
				^((0-((m[0]>>20)&1))&8798212) //8798212=[!2,14,17,18,23!]
				^((0-((m[0]>>18)&1))&2269184) //2269184=[!13,15,17,21!]
				^((0-(m[0]&(1<<11)))&16850944) //16850944=[!13,16,24!]
				^((0-((m[0]>>29)&1))&16826368) //16826368=[!14,15,24!]
				^((0-(m[0]&(1<<12)))&2105344) //2105344=[!13,21!]
				^(rotate_left(m[0],31)&81920) //81920=[!14,16!], 163840=[!15,17!]
				^(rotate_left(m[0],29)&16384) //16384=[!14!], 131072=[!17!]
				;
		Qtp1valsvecptr[t] = Qtp1valsptr;
		step_2();
	}
	return step1ok;
}
bool step_0()
{
	static bool firsttime = true; if (firsttime) { cout << "t0 " << flush; firsttime = false; }
	const unsigned t = 0;
	UPDATE(t);
	bool step0ok = false;
	Qr30[offset+t-2] = rotate_left(Q[offset+t-2],30);
	const uint32 mpartial2 = 0 - sha1_f1(Q[offset+t-1], Qr30[offset+t-2], Qr30[offset+t-3]) - sha1_ac[0] - Qr30[offset+t-4];
	const uint32 metmask = 469762050;
	{
		const uint32 metset1 = 268435456;
		const uint32 Qtp1val = Qvalue[offset+t+1] ^ (Qprev[offset+t+1]&Q[offset+t]) ^ ((~metset1) & 0) ^ (xrng64()&2684354612);
		const uint32 mpartial = mpartial2 - rotate_left(Q[offset+t],5);
		metpartialvec[t] = mpartial;
		uint32* Qtp1valsptr = Qtp1valsvec[t];
		uint32 cur = 0; const uint32 curmask = 0;
		do { cur -= 1; cur &= curmask;
		uint32 Qtp1cur = 0;
		do {
			Q[offset+t+1] = Qtp1cur ^ cur ^ Qtp1val;
			Qtp1cur -= 1; Qtp1cur &= 2684354612^curmask; // 5 bits of freedom
			m[t] = Q[offset+t+1] + mpartial;
			if (0 != ((m[t]^metset1)&469762050)) break;
			if ((m[t]&384)==384) continue;
			uint32 metxorfix = (m[t]^metset1) & 0;
			*(Qtp1valsptr++) = Q[offset+t+1]^metxorfix;
		} while (Qtp1cur != 0);
		} while (cur != 0);
		if (Qtp1valsptr == Qtp1valsvec[t]) return step0ok;
		step0ok = true;
		Qtp1valsvecptr[t] = Qtp1valsptr;
		step_1();
	}
	return step0ok;
}
